时间复杂度和空间复杂度计算

• 定义
• 时间复杂度
• • 常见的时间复杂度量级
  • • 常数阶 O ( 1 ) O(1) O(1)
    • 对数阶 O ( l o g N ) O(logN) O(logN)
    • 线性阶 O ( n ) O(n) O(n)
    • 线性对数阶 O ( l o g N ) O(logN) O(logN)
    • 平方阶 O ( n ² ) O(n²) O(n²)
• 空间复杂度
• • • O ( 1 ) O(1) O(1)
    • O ( n ) O(n) O(n)

定义

不同算法消耗的资源和时间会有很大区别，一般会从时间和空间两个维度去考量。

1.时间维度

执行当前算法所消耗的时间，通常用时间复杂度来描述

2.空间维度

执行当前算法需要占用多少内存空间，通常用空间复杂度来描述

时间复杂度

比较通用的方法是采用 [大O符号表示法]，即 T ( n ) = O ( f ( n ) ) T(n) =O(f(n)) T(n)=O(f(n))

其中， f ( n ) f(n) f(n) 表示每行代码执行次数之和，而 O ( ) O() O() 表示正比例关系，该公式全称为：算法的渐进时间复杂度。

for (i=1; i<=n; ++i){
	j = i;
	j++;
}
           

如上所示，假设每行代码执行的时间相同，用1颗粒时间表示，则第一行代码耗时1个颗粒时间，第二行代码耗时 n n n 个颗粒时间，第三行代码同样耗时 n n n 个颗粒时间，因此总时间为 T ( n ) = 1 + 2 n T(n)=1+2n T(n)=1+2n 个颗粒时间，可以看出该算法耗时随着 n n n 的变化而变化，因此可以将这个算法的时间复杂度表示为 T ( n ) = O ( n ) T(n) =O(n) T(n)=O(n)

常见的时间复杂度量级

常数阶 O ( 1 ) O(1) O(1)

对数阶 O ( l o g N ) O(logN) O(logN)

线性阶 O ( n ) O(n) O(n)

线性对数阶 O ( n l o g N ) O(nlogN) O(nlogN)

平方阶 O ( n ² ) O(n²) O(n²)

立方阶 O ( n ³ ) O(n³) O(n³)

K次方阶 O ( n k ) O(n^k) O(nk)

指数阶 ( 2 n ) (2^n) (2n)

从上至下依次的时间复杂度越来越大，执行的效率越来越低

常数阶 O ( 1 ) O(1) O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是 O ( 1 ) O(1) O(1) ，如：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
           

对数阶 O ( l o g N ) O(logN) O(logN)

int i = 1;
while(i<n){
    i = i * 2;
}
           

上面代码可以看到，在 w h i l e while while 循环里面，每次都将 i i i 乘以 2，乘完之后， i i i 距离 n n n 就越来越近了。试着求解一下，假设循环 x x x 次之后， i i i 就大于 n n n 了，此时这个循环就退出了，即 2 的 x x x 次方等于 n n n，那么 x = l o g 2 n x = log2^n x=log2n，也就是说当循环 l o g 2 n log2^n log2n 次以后，代码执行完毕，因此这个代码的时间复杂度为： O ( l o g n ) O(logn) O(logn)

线性阶 O ( n ) O(n) O(n)

for(i=1; i<=n; ++i){
   j = i;
   j++;
}
           

这段代码， f o r for for循环里面的代码会执行 n n n遍，因此它消耗的时间是随着 n n n的变化而变化，因此这类代码都可以用 O ( n ) O(n) O(n)来表示它的时间复杂度

线性对数阶 O ( l o g N ) O(logN) O(logN)

线性对数阶 O ( n l o g N ) O(nlogN) O(nlogN) 其实非常容易理解，将时间复杂度为 O ( l o g n ) O(logn) O(logn) 的代码循环N遍，那么它的时间复杂度就是 n ∗ O ( l o g N ) n*O(logN) n∗O(logN)，也就是了O(nlogN)

将以上代码加一点修改来举例：

for(m=1; m<n; m++){
    i = 1;
    while(i<n){
        i = i * 2;
    }
}
           

平方阶 O ( n ² ) O(n²) O(n²)

将 O ( n ) O(n) O(n) 的代码再嵌套一遍，其时间复杂度即为 O ( n ² ) O(n²) O(n²)

for(x=1; i<=n; x++){
   for(i=1; i<=n; i++){
       j = i;
       j++;
    }
}
           

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，用 S ( n ) S(n) S(n) 来定义，较为常用的有 O ( 1 ) O(1) O(1)， O ( n ) O(n) O(n)， O ( n 2 ) O(n^2) O(n2)

O ( 1 ) O(1) O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
           

代码中的 i 、 j 、 m i、j、m i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S ( n ) = O ( 1 ) S(n) = O(1) S(n)=O(1)

O ( n ) O(n) O(n)

int[] m = new int[n];
for(i=1; i<=n; ++i){
   j = i;
   j++;
}
           

第一行代码new了一个数组出来，这个数据占用的大小为 n n n，这段代码的2-5行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S ( n ) = O ( n ) S(n) = O(n) S(n)=O(n)

知乎链接：https://zhuanlan.zhihu.com/p/50479555

本文原创发布于微信公众号「 不止思考 」，欢迎关注，交流更多的 互联网认知、工作管理、大数据、Web、区块链技术。