我们知道，解决同一个问题，可能会有不同的算法，这些算法最终结果也许是一样的，但是在计算过程中占用的内存空间和计算的时间却会有不同的区别，而这两个维度「时间」和「空间」就是衡量一个算法优劣的标准。
- 时间维度：指执行当前算法所消耗的时间，通常用「时间复杂度」来描述
- 空间维度：指执行当前算法占用的内存空间，通常用「空间复杂度」来描述 因此，评价一个算法的效率主要看它的时间复杂度和空间复杂度，很多时候优秀的算法跟其他解决同一个问题的其他算法相比，在时间或空间都能得到明显的降低。
# 时间复杂度
时间复杂度是我们理论上讨论一个算法的耗时，这样就可以不受环境的影响，用一种通用的方法：大O符号表示法，即T(n) = O(f(n))。
先来看个例子
var a = 0
for (i = 0; i < n; i++) { // 执行了n次
a += i // 执行了n次
}
2
3
4
在大O表示法中，f(n)表示每行代码执行次数之和，O表示正比例关系，这个公式的全称是: 算法的渐进时间复杂度。意思是当n趋于无穷大的时候，如果T(n)/f(n)的极限值是一个不为零的常数，那么f(n)就是T(n)的同数量级函数。
我们看回这个例子，假设每一行代码的执行时间都是一样的，用t表示，第一行代码执行了n次，第二行代码执行了n次，即f(n) = (2 * n)，T(n) = (2 * n) * t，可以看出这个算法的耗时是随着n的变化不断变化的，这里我们根据下面的规则简化一下这个公式：
- 用常数1取代运行时间中的所有加法常数
- 只保留最高阶项
- 去除最高阶的常数
经过简化，T(n) = O(n)，就是上述例子的时间复杂度为O(n)，为什么可以这样简化呢？是因为大O表示法并不是用于真实的代表算法的执行时间，它是表示代码执行时间的增长变化趋势的。如果n趋于无穷大，T(n) = (2 * n) * t的倍数2意义不大，可以简化为T(n) = O(n)表示即可。
# 常见的时间复杂度
| 描述 | 增长的数量级 | 表示 |
|---|---|---|
| 常数阶 | 1 | O(1) |
| 对数阶 | logN | O(logN) |
| 线性阶 | n | O(n) |
| 线性对数阶 | nlogN | O(nlogN) |
| 平方阶 | n^2 | O(n^2) |
| 立方阶 | n^3 | O(n^3) |
| k次方阶 | n^k | O(n^k) |
| 指数阶 | 2^n | O(2^n) |
从上到下的时间复杂度越来越大，执行的效率越来越低
# 常数阶O(1)
典型的代码：
a = b + c
这类型代码无论执行了多少行，只要没有循环等复杂结构，那么这个代码的时间复杂度就是O(1)
# 线性阶O(n)
var a = 0
for (var i = 0; i < n; i++) {
a += i
}
2
3
4
正如前面的分析，这类代码的时间复杂度O(n)
# 对数阶O(logn)
var a = 1
while (a < n) {
a *= 2
}
2
3
4
从上面代码可以看到，在while循环里，每次都将a乘于2，假设这个循环体执行了x次，那么2 ^ x = n，x = log2n，去除常数简化后为，O(logn)
# 线性对数阶O(nlogn)
将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂就是n*O(logn), 也就是O(nlogn)
for (let m = 0; m < n; m++) {
var a = 1
while (a < n) {
a *= 2
}
}
2
3
4
5
6
# 平方阶O(n^2)
把O(n)的代码在嵌套循环一次，那么它的时间复杂度就是O(n^2)
for (var j = 0; j < n; j++) {
var a = 0
for (var i = 0; i < n; i++) {
a += i
}
}
2
3
4
5
6
这个代码嵌套了2层n循环，它的时间复杂度就是O(n^2)， 如果把外层循环的n改为m，即
for (var j = 0; j < m; j++) {
var a = 0
for (var i = 0; i < n; i++) {
a += i
}
}
2
3
4
5
6
那么时间复杂度就变为O(m * n) 立方阶和k次方阶也是以此类推。
# 空间复杂度
空间复杂度表示一个算法在运行过程中临时占用存储空间大小的一个量度，用S(n)表示
# 空间复杂度O(1)
a = b + c
代码中a, b, c所分配的空间不随处理数据量的变化而变化，空间复杂度S(n)=O(1)
# 空间复杂度O(n)
var arr = new Array(n)
这里新生成了一个数组，占用大小为n，即S(n)=O(n)
# 总结
本文对几种常见的时间复杂度和空间复杂度进行基础分析，衡量一个算法的优劣要结合时间复杂度和空间复杂度来衡量，有些算法会牺牲空间换时间，这里就看怎么去找到一个平衡点使得算法效率高且优雅了。