ag-时间/空间复杂度

一、说明

时间复杂度和空间复杂度是用来评价算法效率高低的2个标准。
时间复杂度：执行算法需要消耗的时间长短。
空间复杂度：执行当前算法需要消耗的存储空间大小。

表示方法
一般用“大O符号表示法”来表示时间复杂度：T(n) = O(f(n))
n是影响复杂度变化的因子，f(n)是复杂度具体的算法。

常见的时间复杂度度量级：

常数阶O(1)
线性阶O(n)
对数阶O(logN)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)

int a = 1;
int b = 2;
int c = 3;

是不是这段代码的时间复杂度表示为O(n)呢？
其实不是的，因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。
上面的算法并没有随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

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

第1行会执行1次，第2行和第3行会分别执行n次，总的执行时间也就是 2n + 1 次。
所以它的时间复杂度其实是O(n)。

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

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

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

把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。
立方阶O(n³)、K次方阶O(n^k) 参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。

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

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

评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。可能有的开发者接触时间复杂度和空间复杂度的优化不太多（尤其是客户端），但在服务端的应用是比较广泛的，在巨大并发量的情况下，小部分时间复杂度或空间复杂度上的优化都能带来巨大的性能提升，是非常有必要了解的。

暂无