image.png
正式工作也有3年的时间了，想要写出更加优雅的代码。
所以最近在刷leetcode补充数据结构和算法方面的知识。
学校里虽然学过，但是仅仅是有个大概的认识。只有实际工作过几年以后，才会明白数据结构和算法的重要性。
如果是通信专业出身的同学，或者是硬件出身的同学一定知道：对于一个信号，我们可以从时域和频域两个方面去分析。
那么计算机科学或者说软件开发中的算法怎么去分析呢？
有两个衡量优劣的维度：时间复杂度和空间复杂度。
- 时间复杂度：执行当前算法所消耗的'时间'。
- 空间复杂度：执行当前算法所占用的内存。
在这边博文中，我们来好好分析一下时间复杂度。
- 时间复杂度真的是计算'时间'吗？
- 时间复杂度公式：大O符号表示法
- 常见时间复杂度类型及代码分析
- 常数型O(1)
- 对数型O(log n)
- 线性型O(n)
- 线性对数型O(n log n)
- 平方型O(n2)、立方型O(n3)、K次方型O(n^k)
- 平方底指数型O(2n)、立方底指数型O(3n)、K次底指数型O(k^n)
- 阶乘型O(n!)
- 如何理解斐波那契数列的时间复杂度O(2^N)?
- 如何理解阶乘型时间复杂度O(n!)？
- 参考资料
时间复杂度真的是计算'时间'吗？
把算法的执行时间当做时间复杂度？
这种方式是最为直观也是最容易想到的方式。
但是有一个问题，那就是代码在不同性能的机器上运行，以及在不同的状态下运行，会呈现出完全不同的运行时间。
比如说我有一台内存为32GB内存的mbp，还有一台8GB的台式机，假设其它的硬件条件比如cpu，主板以及机器负载状态一致。通常情况下，32GB的内存要比8GB的内存运行更快。而且这种理想状态下的只有单一变量的状态也是很难做到的。
所以不能通过计算算法的消耗时间作为时间复杂度。
那我们通常所说的'时间'复杂度中的'时间'到底是指什么呢？
聪明的前辈们想到了一种方式：大O表示法。
大O表示法内部有非常复杂的数学计算逻辑，我们偷个懒，不去证明公式，把公式用好就很厉害了。
为什么不去证明一下或者演算一遍？
我在大一曾经上过一门叫做高等代数的课，有道题目叫做：请证明1+1=2。
看到这个题目应该知道为什么不深究大O表示法背后的数学了吧。
时间复杂度公式：大O符号表示法
T(n) = O(f(n))
- f(n)是指每行代码执行次数之和
- f(n)可以是这些值：1，log n，n，nlog n，n2，n3，nk，2n，n!
- f(n)与O正相关
- O(f(n))可以是这些值：O(1)，O(log n)，O(n)，O(nlog n)，O(n2)，O(n3)，O(nk)，O(2n)，O(n!)
- 大O表示法实际表示的是代码执行时间的增长变化趋势，不是真实的运行时间，是一种趋势预估
- 大O表示法中的f(n)是近似值。很多时候不会完全是1，log n，n，nlog n，n2，n3，nk，2n，n!这些完整的值。例如斐波那契数列的真实时间复杂度为O(2N-1)，由于N->∞，所以可以近似为O(2N)。
更多的斐波那契数列时间复杂度的分析可以查看下文中的：如何理解斐波那契数列的时间复杂度O(2^N)?
常见时间复杂度类型及代码分析
理论扯了一大堆了，到精彩绝伦的Show me the code环节了。
先来看一张大O复杂度曲线图。
image
以下时间复杂度根据最佳->较好->一般->较差->糟糕的顺序排列。
- 常数型O(1)
- 对数型O(log n)
- 线性型O(n)
- 线性对数型O(n log n)
- 平方型O(n2)、立方型O(n3)、K次方型O(n^k)
- 平方底指数型O(2n)、立方底指数型O(3n)、K次底指数型O(k^n)
- 阶乘型O(n!)
常数型O(1)
- 常见于赋值和引用等简单操作
- 算法消耗不随变量增长而增长，性能最佳
- 无论代码执行多少行，即使有几千几万行，时间复杂度都为O(1)
- 实际开发过程中，一次递归的时间复杂度也为O(1)。因为O(1^n)无论n为多少都为O(1)
let i = 0;
let j = 9;
i++;
j--;
let k = i + j;
代码分析：
i为1，j为10，k为11。
时间复杂度为O(1)。
对数型O(log n)
- 常用代码执行次数为x，n为目标数字。符合2^x=n，推导出x=log2(n)（log n）的情况
- 算法消耗随n的增长而增长，性能较好
let n = 100;
let i = 1;
while(i<n){
i = i * 2
}
代码分析：
i为128。
n为100，时间复杂度为O(log2(100))。
因为Math.log2(100)≈6.64，所以最终的时间复杂度为O(6.65)。
线性型O(n)
- 常见于一次for循环，while循环
- 算法消耗随n的增长而增长，性能一般
- 无论n值有多大，即使是Inifinity，时间复杂度都为O(n)
let n = 100;
let j = 0;
for(let i = 0;i<n;i++){
j = i;
}
代码分析：
i为100，j为99。
n为100，时间复杂度为O(100)。
线性对数型O(n log n)
- 常用于一个对时间复杂度为O(log2(n))的代码执行一个n次循环
- 算法消耗随n的增长而增长，性能较差
let n = 100;
for(let m = 0; m<n; m++){
let i = 1;
while(i<n){
i = i * 2
}
}
代码分析：
i为128。
m为100，n为100，时间复杂度为O(m log2(n))。
因为100* Math.log2(100)≈664.39，所以最终的时间复杂度为O(664.39)。
平方型O(n2)、立方型O(n3)、K次方型O(n^k)
- 最常见的算法时间复杂度，可用于快速开发业务逻辑
- 常见于2次for循环，或者3次for循环，以及k次for循环
- 算法消耗随n的增长而增长，性能糟糕
- 实际开发过程中，不建议使用K值过大的循环，否则代码将非常难以维护
let n = 100
let v = 0;
for(let i =0;i<n;i++){
for(let j = 0; j<n; j++){
v = v+j+i;
}
}
代码分析：
v为990000，i为100，j为100.
n为100，时间复杂度为O(100^2)。
也就是O(10000)。
立方型O(n3)、K次方型O(nk)和平方型O(n^2)类似，无非是多了几次循环。
// 立方型O(n^3)
for(let i =0;i<n;i++){
for(let j = 0; j<n; j++){
for(let m = 0; m<n; m++){
}
}
}
// K次方型O(n^k)
for(let i =0;i<n;i++){
for(let j = 0; j<n; j++){
for(let m = 0; m<n; m++){
for(let p = 0; p<n; p++){
... // for循环继续嵌套下去，k值不断增大
}
}
}
}
平方底指数型O(2n)、立方底指数型O(3n)、K次底指数型O(k^n)
- 常见于2次递归的情况，3次递归以及k次递归的情况
- 算法消耗随n的增长而增长，性能糟糕
- 实际开发过程中，k为1时，一次递归的时间复杂度为O(1)。因为O(1^n)无论n为多少都为O(1)。
斐波那契数列（兔子数列、黄金分割数列）：1、1、2、3、5、8、13、21、34···
题目：leetcode 509 斐波那契数
题解：[509.斐波那契数列 (Fibonacci Number)]https://github.com/FrankKai/leetcode-js/blob/master/509.Fibonacci_Number.js)
/**
* @param {number} N
* @return {number}
*/
var fib = function (N) {
/**
* 解法1: 递归
* 性能: 88ms 34.2MB
* 时间复杂度：O(2^N)
*/
if (N <= 1) return N;
return fib(N - 1) + fib(N - 2);
};
假设N等于100。
代码分析：
结果为 xxx。
因为浏览器直接卡死。nodejs中也运行不出来。
具体原因则是2的100次方真的太大了。算不来。
N为100，时间复杂度为O(2^100)。
因为Math.pow(2, 100)= 1.2676506002282294e+30，所以最终的时间复杂度为O(1.2676506002282294e+30)。大到爆表。
立方底指数型O(3n)、K次底指数型O(kn)与平方底指数型O(2^n)类似，只不过基数变为了3和k。
O(Math.pow(3, n))
O(Math.pow(k, n))
假设n为100，假设k为5。
Math.pow(3, n)为5.153775207320113e+47。
Math.pow(5, n)为7.888609052210118e+69。
时间复杂度也是巨高，真的是指数爆炸💥。
更多的斐波那契数列时间复杂度O(2N）的分析可以查看下文中的：如何理解斐波那契数列的时间复杂度O(2N)?
阶乘型O(n!)
- 极其不常见
- 算法消耗随n的增长而增长，性能糟糕
function nFacRuntimeFunc(n) {
for(let i=0; i<n; i++) {
nFacRuntimeFunc(n-1);
}
}
阶乘型O(n!)的时间复杂度按照(n!+(n-1)!+(n-2)!+ ··· + 1) +((n-1)!+(n-2)!+ ··· + 1)+ ··· 的方式去计算。
注意哦，这里是多个阶乘的和。不仅仅是n * (n-1) * (n-2) * (n-3)···1。
假设n从0到10，它的算法复杂度O(n!)依次为1，4，15，64，325，1956，13699，109600，986409，9864100···
为了和上文中的其它算法复杂度做比较，n为100时是多少呢？
O(2n)为10才是1024，n为100时O(2n)直接浏览器卡死了。
O(n!)才为10就接近1000万了，真要是n设置成100，计算到机器烧了也计算不出吧。
所以n为100时的O(n!)就不要想了，庞大到恐怖的一个数字。
更多的阶乘型时间复杂度O(n!)的分析可以查看下文中的：如何理解阶乘型算法复杂度O(n!)？
如何理解斐波那契数列的时间复杂度O(2^N)?
O(2^N)
-
Math.pow(base, ex)，2个递归所以base是2。 - N的话是因为N->∞，但其实真正是O(2^(N-1))。
/**
* @param {number} N
* @return {number}
*/
var fib = function (N) {
/**
* 解法1: 递归
* 性能: 88ms 34.2MB
*/
console.log('foo');
if (N <= 1) return N;
return fib(N - 1) + fib(N - 2)
};
| N | 打印foo数 | O(2^N) |
|---|---|---|
| 1 | 1 | O(2^0) |
| 2 | 2^1 + 1 | O(2^1) |
| 3 | 2^2 + 1 | O(2^2 ) |
| 4 | 2^3 + 1 | O(2^3 ) |
| 5 | 2^4 + 1 | O(2^4 ) |
通过上表我们分析得到：
如果包含1的话，严格来讲时间复杂度是O(2^(N-1))。
如果从N>1开始计算，时间复杂度确实是O(2^N)。
斐波那契数列非常长，N->∞，因此可以将斐波那契数列的时间复杂度直接看做是O(2^N)。
如何理解阶乘型时间复杂度O(n!)？
O(N!)
我们把上面的代码改造一下，增加一个count用来统计O(n!)。
let count = 0;
function nFacRuntimeFunc(n) {
for(let i=0; i<n; i++) {
count++;
nFacRuntimeFunc(n-1);
}
}
阶乘型O(n!)的时间复杂度按照(n!+(n-1)!+(n-2)!+ ··· + 1) +((n-1)!+(n-2)!+ ··· + 1) 的方式去计算。
注意哦，这里是多个阶乘的和。不仅仅是n * (n-1) * (n-2) * (n-3)···1。
上述示例中的count即为复杂度的值。
| n | 多次n! + (n-1)! + ··· + 1! | count | O(n!) |
|---|---|---|---|
| 1 | 1 | 1 | O(1) |
| 2 | (2!+1!) +(1!) | 4 | O(4) |
| 3 | (3!+(2!+1!)+1!)+((2!+1!)+1!)+(1!) | 15 | O(15) |
| 4 | ... | 64 | O(64) |
| 5 | ... | 325 | O(325) |
| 6 | ... | 1956 | O(1956) |
| 7 | ... | 13699 | O(13699) |
| 8 | ... | 109600 | O(109600) |
| 9 | ... | 986409 | O(986409) |
| 10 | ... | 9864100 | O(9864100) |
快看看这个表格吧，n为10的时候O(n!)达到了O(9864100)，接近了O(一千万)。这种算法的性能真的是糟糕到极致了。
参考资料
https://juejin.im/post/5e7c0946f265da42e879fe0c
https://zhuanlan.zhihu.com/p/50479555
https://www.bigocheatsheet.com/
https://stackoverflow.com/questions/3953244/example-of-on
期待和大家交流，共同进步，欢迎大家加入我创建的与前端开发密切相关的技术讨论小组：
- 微信公众号： 生活在浏览器里的我们 / excellent_developers
- Github博客: 趁你还年轻233的个人博客
- SegmentFault专栏：趁你还年轻，做个优秀的前端工程师
- Leetcode讨论微信群：Z2Fva2FpMjAxMDA4MDE=（加我微信拉你进群）
image
努力成为优秀前端工程师！
网友评论