时间和空间复杂度
前言
评估一个算法的好坏可以通过它的时间复杂度和空间复杂度来分析出来。
- 时间复杂度：表示算法执行的耗时。
- 空间复杂度：表示算法执行过程中临时的存储空间占用的内存大小。
它们都可以用大O表示法来表示：
时间复杂度一般有：O(1)、O(logN)、O(n)、O(nlogN)、O(n^2)、O(n^3)、O(2^n)
空间复杂度一般有：O(1)、O(n)、O(n^2)
时间复杂度的通用公式为
T(n) = O(f(n))，
- T(n)表示代码的执行时间。
- n表示数据规模的大小。
- f(n)表示每行代码执行的次数总和，因为是一个公式，所以用f(n)表示。
- 公式中的O，表示代码的执行时间T(n)与f(n)表达式成正比。
效率图比较
图像来自：函数图像绘制
时间复杂度
O(1)：常数阶
function fn1(grade) {
// 只会执行一次
if (grade > 90) {
console.log('优秀');
} else if (grade > 80) {
console.log('良好');
} else if (grade > 60) {
console.log('及格');
} else {
console.log('不及格');
}
}
/*
无论怎样，只会执行一次
所以时间复杂度为 O(1)
*/O(logN)：对数阶
function fn(n) {
let i = 1
while (i < n) {
i = i * 2
}
}
/*
分析：假设执行了 x 次，i就大于n跳出了循环
也就是说 2^x = n
所以 x = log2(n)
所以用大O表示法，O(logN)
*/O(n)：线性阶
function fn2(n) {
let sum = 0 // 执行一次 1
/*
for循环中的
let i = 1，执行一次 1
i<=n 执行n次 n
i++ 执行n次 n
sum = sum +i 执行n次 n
*/
for (let i = 1; i <= n; i++) {
sum = sum + i
}
return sum // 执行一次 1
}
/*
所以上面的程序最终执行次数为
1+1+3n+1 = 3+3n
所以使用大O表示法为 O(n)
*/O(nlogN)：线性对数阶
function fn(n) {
// i+=i相当于 i=i+i=2i 每次都乘以2，看乘了多少次2会大于n，所以执行了 log2(n)次后就大于n
// 所以外城循环执行了 1+2log2(n)次，内层循环执行了log2(n)*(1+3n)次
// 最终共执行了，1+2log2(n) + log2(n)*(1+3n) = 1+3log2(n)+3nlog2(n)
for (let i = 1; i < n; i += i) {
for (let j = 0; j < n; j++) {
console.log('aaa');
}
}
}
/*
所以上面的使用大O表示，为O(nlog(N))
*/O(n^2)：平方阶
function fn(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log('aaa');
}
}
}
/*
外层循环 1+2n
内层循环 n*(1+3n)
所以最终执行 1+2n+n*(1+3n) = 1+3n+3n^2
使用大O表示法，最终为 O(n^2)
*/O(n^3)：立方阶
function fn(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let m = 0; m < n; m++) {
console.log('aaa');
}
}
}
}
/*
外层循环 1+2n
第二层循环 n*(1+2n)
第三层循环 n^2(1+3n)
所以最终执行 加起来，只看最内层执行的次数 就是三次幂了
使用大O表示法，最终为 O(n^3)
*/O(2^n)：指数阶
/*
菲波那切数列的递归解法
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
下标 0 1 2 3 4 5 6 7 8 9
值 0 1 1 2 3 5 8 13 21 34
*/
function fn(n) {
// 出口
if (n <= 1) return n
return fn(n - 1) + fn(n - 2)
}
console.log(fn(3)); // 2
console.log(fn(4)); // 3
console.log(fn(9)); // 34时间复杂度为 O(2^n)
空间复杂度
空间复杂度 O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
jslet i = 1; let j = 2; ++i; j++; let m = i + j;代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)
空间复杂度 O(n)
jslet arr = [] for(let i = 0; i<n; i++){ arr.push(i) }数组刚开始初始化时，长度为零，当随着循环的执行，数组的长度变为了n，申请的临时空间也变为了n，所以空间复杂度就为O(n)
所以，如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1)；反之，如果有关，则需要进一步判断它们之间的关系：
- 如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;
- 如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 表示；
- 如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 表示；
- 等等。
在多数场景中，一个好的算法往往更注重的是时间复杂度的比较，而空间复杂度只要在一个合理的范围内就可以。
例子1 菲波那切数列
for循环的解法
js/* 菲波那切数列 f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2) 下标 0 1 2 3 4 5 6 7 8 9 值 0 1 1 2 3 5 8 13 21 34 */ function fn(n) { if (n <= 1) return n let first = 0 let second = 1 // 如果求下标2 需要加1次 0+1=1 // 如果求下标3 需要加2次 0+1=1 1+1=2 // 所以如果求下标n 需要加 n-1次 for (let i = 0; i < n - 1; i++) { let sum = first + second first = second second = sum } return second } console.log(fn(3)); // 2 console.log(fn(4)); // 3 console.log(fn(9)); // 34它的时间复杂度为O(n)。空间复杂度也为O(n)。
递归的解法
js/* 菲波那切数列 f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2) 下标 0 1 2 3 4 5 6 7 8 9 值 0 1 1 2 3 5 8 13 21 34 */ function fn(n) { // 出口 if (n <= 1) return n return fn(n - 1) + fn(n - 2) } console.log(fn(3)); // 2 console.log(fn(4)); // 3 console.log(fn(9)); // 34图片来自：https://www.bilibili.com/video/BV1sX4y1G7oM?p=9&spm_id_from=pageDriver
所以最终的时间复杂度为：O(2^n)，空间复杂度为O(1)
例子2 推导时间复杂度
设某算法时间表示为递推关系T(n) = T(n-1) +n，n为整数，及T(0)=1，计算该算法的时间复杂度。
T(n) = T(n-1) +n
= T(n-2) + (n-1) +n
= T(n-3) + (n-2) + (n-1) + n
...
= T(1) + 2 + 3 + ... + (n-2) + (n-1) + n
= T(0) + 1 + 2 + 3 + ... + (n-2) + (n-1) + n
= 1 + 1 + 2 + 3 + ... + (n-2) + (n-1) + n
= 1 + (1 + n)*n / 2
= O(n^2)总结
时间复杂度的大小：
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(nlog(n))< O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)
注意，这里仅介绍了以最坏情况下的频度作为时间复杂度，而在某些实际场景中，还可以用最好情况下的频度和最坏情况下的频度的平均值来作为算法的平均时间复杂度。
参考
https://www.bilibili.com/video/BV1sX4y1G7oM?p=9&spm_id_from=pageDriver