时间复杂度和空间复杂度

[chris-paul]

如何表示复杂度

如何表示算法复杂度，具体来讲就是代码执行的时间、执行消耗的存储空间。例如:

function cal(n) {
    let sum = 0; // 1 unit_time
    let i = 0; // 1 unit_time
    for(; i <= n; i++) { // n unit_time
        sum += i; // n unit_time
    }
    return sum
}

从 CPU 的角度看，每段代码不过是读写数据或操作数据，尽管每次操作 CPU 执行的个数、执行的时间都不同，但我们粗咯把每次执行的时间都一致，称为 unit_time

所以上述代码总共执行 (2n+2)*unit_time 时间，即：T(n)=(2n+2)*unit_time ，所以，我们可以写成:

T(n) = O(f(n))

其中：

• n：表示数据规模的大小

• f(n)：表示每行代码执行的次数总和,也就是2n + 2

• O：表示代码的执行时间 T(n) 与 f(n) 表达式成正比

当 n 很大时，例如 10000，甚至更大，T(n) = O(f(n)) 可以表示为 T(n) = O(n) 。

这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

时间复杂度

当 n 无限大时，时间复杂度 T(n) 受 n 的最高数量级影响最大，与f(n) 中的常量、低阶、系数关系就不那么大了。所以我们分析代码的时间复杂度时，仅仅关注代码执行次数最多的那段就可以了

function fun1(n) {
    let sum = 0,i = 0; 
    for(; i <= n; i++) {
        sum += i; 
    }
    return sum
}
function fun2(n) {
    let sum = 0, sum1 = 0, i = 0, j = 0; 
    for(; i <= n; i++) { // 循环1
        sum += i; 
    }
    for(i = 0; i <= n; i++) { // 循环2
        for(j = 0; j <= n; j++) { 
            sum += i * j; 
        }
    }
    return sum
}
function fun3(n) {
    let sum = 0, i = 0; 
    for(; i <= n; i++) { 
        sum += fun(i); 
    }
    return sum
}

fun1 中第1行都是常量，对 n 的影响不大，所以总的时间复杂度要看第2、3行的循环，即时间复杂度为： O(n)

fun2 中循环1的时间复杂度为 O(n) ，循环2的时间复杂度为 O(n2)，当 n 趋于无穷大时，总体的时间复杂度要趋于 O(n²) ，即上面代码的时间复杂度是 O(n²)

fun3 的时间复杂度是 O(n * T(fun)) = O(n*n) ，即 O(n²)

所以：T(c+n)=O(n)，T(m+n)=O(max(m, n))，T(n) = T1(n) T2(m) = O(nm)，其中 c 为常量

常见复杂度（按数量阶递增）

多项式量级：

• 常量阶： O(1)：当算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)

• 对数阶：O(logn): 每次循环 i 都乘以 2 ，直至 i > n ，即执行过程是：2⁰、2¹、2²、…、2^k、…、2^x、 n
  所以总执行次数 x ，可以写成 2^x = n ，则时间复杂度为 O(log₂n) 。这里是 2 ，也可以是其他常量 k ，时间复杂度也是： O(log₃n) = O(log₃2 * log₂n) = O(log₂n)

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

• 线性阶：O(n)

• 线性对数阶：O(nlogn),归并排序、快排的时间复杂度

• 平方阶、立方阶、….、k次方阶：O(n²)、O(n³)、…、O(n^k),循环里嵌套一层循环的复杂度，冒泡排序、插入排序等排序的复杂度O(n²)

非多项式量阶

• 指数阶：O(2^k)，已经是很难接受的时间效率，如未优化的斐波拉契数列的求值

• 阶乘阶：O(n!)

如果a的x次方等于N（a>0，且a不等于1），那么数x叫做以a为底N的对数，记作x=logaN。其中，a叫做对数的底数，N叫做真数

递归函数的时间复杂度

如果一个递归函数再每一次调用自身时，只是调用自己一次，那么它的时间复杂度就是这段递归调用栈的最大深度

使用递归对一段字符串进行翻转，因为每次调用都会截取字符串的最后一位，所以这段程序的递归调用次数就是递归的深度，也就是字符串自身的长度，也就是O(n)，这也是递归最简单的调用，每一次只调用自身一次

function reversetStr (s) {
	if (s === '') {
    	return ''
    }
	return s[s.length - 1] + reversetStr(s.slice(0, -1))
}

接下来我们使用递归求解斐波拉契数列，也就是这样的一堆数，后面一个数等于前面两个之和

1 1 2 3 5 8 13 21 34 55 89 ...

function fib (n) {
	if (n === 1 || n === 2) {
    	return n
    }
    return fib(n - 1) + fib(n - 2)
}

这个递归函数在调用自身的时，又调用了两次自身,我们可以看到，当要计算7时，需要计算出6和5；当要计算6和5时，又要分别计算出5和4以及4和3；每次这颗递归树展开的叶子节点都是上一层的两倍，也就说这是一个指数级的算法，时间复杂度为O(2ⁿ)

其他几种复杂度分析

以上说的时间复杂度指的是一段程序的平均时间复杂度，其实还会有最坏时间复杂度，最好时间复杂度以及均摊时间复杂度

• 最好时间复杂度：例如我们要从数据里找到一个数字，数组的第一项就符合要求，这个时候就表示数组取值最好的时间复杂度是O(1)，当然了这种概率是极低的，所以并不能作为算法复杂度的指导值

• 最坏时间复杂度：数组取值直到最后一个才找到符合要求的，那就是需要O(n)的复杂度；又例如快排的平均时间复杂度是O(nlogn)，但一个没经过优化的快排去处理一个已经排好序的数组，会退化成O(n²)

• 均摊时间复杂度：表示的是一段程序出现最坏和最好的频次不同，这个时候复杂度的分析就是将它们的操作进行均摊，取频次的多操作，然后得出最终的复杂度

空间复杂度

时间复杂度表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度表示算法的存储空间与数据规模之间的增长关系。例如

function test(arr) {
    const a = 1
    const b = 2
    let res = 0
    for (let i = 0; i < arr.length; i++) {
    	res += arr[i]
    }
    return res
}

我们定义了三个变量，空间复杂度是O(3),又是常数级别的，所以这段程序的空间复杂度又可以表示为O(1)。只用记住是另外开辟的额外空间，例如额外开辟了同等数组大小的空间，数组的长度可以表示为n，所以空间复杂度就是O(n)，如果开辟的是二维数组的矩阵，那就是O(n²)，因为空间度基本也就是以上几种情况，计算会相对容易

function fun(n) {
    let a = [];
    for (let i = 0; i < n; i++) {
        a.push(i);
    }
    return a;
}

以上代码我们可以清晰的看出代码执行的空间为 O(1+n) = O(n)，即为 i 及数组 a 占用的储存空间。

参考链接

• 前端进阶算法1：如何分析、统计算法的执行效率和资源消耗？ sisterAn/JavaScript-Algorithms#1

• https://leetcode-cn.com/app/circle/article/bWiGTj/?isDark=false&rawContent=false