如何衡量算法的复杂度?有哪些衡量角度、采用何种表示方式?
时间: 2023-06-13 07:08:23 浏览: 97
算法的复杂度可以从时间复杂度和空间复杂度两个方面进行衡量。
时间复杂度是指算法在执行过程中所需要的时间资源,通常以“大O符号”表示,表示最坏情况下算法的时间复杂度。
空间复杂度是指算法在执行过程中所需要的内存资源,也通常以“大O符号”表示,表示最坏情况下算法的空间复杂度。
常见的时间复杂度从小到大排序为:O(1)、O(log n)、O(n)、O(nlog n)、O(n^2)、O(n^3)、O(2^n)、O(n!)。其中,O(1)表示算法的执行时间与问题规模无关;O(log n)表示算法的执行时间与问题规模的对数成正比;O(n)表示算法的执行时间与问题规模成正比;O(n^2)表示算法的执行时间与问题规模的平方成正比;O(2^n)表示算法的执行时间呈指数级增长。
常见的空间复杂度从小到大排序为:O(1)、O(log n)、O(n)、O(nlog n)、O(n^2)、O(n^3)、O(2^n)、O(n!)。其中,O(1)表示算法所需要的额外空间与问题规模无关;O(log n)表示算法所需要的额外空间与问题规模的对数成正比;O(n)表示算法所需要的额外空间与问题规模成正比。
通常,算法的复杂度可以用时间和空间复杂度的组合来表示。例如,O(n)的时间复杂度和O(1)的空间复杂度可以表示为O(n);O(n^2)的时间复杂度和O(n)的空间复杂度可以表示为O(n^2)。
阅读全文
相关推荐















