时间复杂度 和 空间复杂度

发表于 分类于 阅读次数：

概念

时间复杂度和空间复杂度是用来评价算法效率高低的两个标准。

  • 时间复杂度：就是执行算法需要消耗的时间长短，越快越好。
  • 空间复杂度：就是执行当前算法需要消耗的存储空间大小，也是越小越好。

时间复杂度计算

表示方法

我们一般用“大O符号表示法”来表示时间复杂度：$T(n) = O(f(n))$

  • $n$是影响复杂度变化的因子
  • $f(n)$是复杂度具体的算法。
常见时间复杂度
  • 常数阶 $O(1)$
  • 线性阶 $O(n)$
  • 对数阶 $O(logN)$
  • 线性对数阶 $O(nlogN)$
  • 平方阶 $O(n^2)$
  • 立方阶 $O(n^3)$
  • K次方阶 $O(n^k)$
  • 指数阶 $O(2^n)$
常数阶$O(1)$
1
2
3
$a = 1;
$b = 2;
$c = 3;

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

线性阶$O(n)$
1
2
3
4
for($i = 1; $i <= n; $i++) {
    $j = $i;
    $j++;
}

看这段代码会执行多少次呢？
第1行会执行1次，第2行和第3行会分别执行$n$次，总的执行时间也就是$2n+1$次，那它的时间复杂度表示是 $O(2n + 1)$ 吗？ No !
还是那句话：“大$O$符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的”。
所以它的时间复杂度其实是$O(n)$。

对数阶$O(logN)$
1
2
3
4
$i = 1;
while($i < n) {
    $i = $i * 2;
}

可以看到每次循环的时候 i 都会乘2，那么总共循环的次数就是$log_{2}n$，因此这个代码的时间复杂度为$O(logn)$。
这儿有个问题，为什么明明应该是$O(log_{2}n)$,却要写成$O(logn)$呢？
其实这里的底数对于研究程序运行效率不重要，写代码时要考虑的是数据规模$n$对程序运行效率的影响，常数部分则忽略，同样的，如果不同时间复杂度的倍数关系为常数，那也可以近似认为两者为同一量级的时间复杂度。

线性对数阶$O(nlogN)$
1
2
3
4
5
6
for($m = 1; $m < $n; $m++) {
    $i = 1;
    while($i < $n) {
        $i = $i * 2;
    }
}

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

平方阶$O(n^2)$
1
2
3
4
5
6
for($x=1; $i <= $n; $x++){
   for($i = $1; $i <= $n; $i++) {
       $j = $i;
       $j++;
    }
}

把 $O(n)$ 的代码再嵌套循环一遍，它的时间复杂度就是 $O(n^2)$ 了。

立方阶$O(n^3)$、K次方阶$O(n^k)$

参考上面的$O(n^2)$去理解就好了，$O(n^3)$相当于三层n循环，其它的类似。

空间复杂度计算

空间复杂度$O(1)$

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

1
2
3
4
5
$i = 1;
$j = 2;
++$i;
$j++;
$m = $i + $j;

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

空间复杂度$O(n)$
1
2
3
4
5
$m = array(1,2,3,.....,n);
for($i=1; $i <= $n; ++$i) {
   $j = $i;
   $j++;
}

这段代码中，第一行初始化一个数组出来，这个数据占用的大小为$n$，后面虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 $S(n) = O(n)$。