时间复杂度
维基百科：在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行 时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大 O 符号表述，不包括这个函数的低阶 项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如， 如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 5n^3 + 3n 的时间运行完毕，那 么它的渐近时间复杂度是 O(n3)。
名词解释：
- n：问题的规模，n 是不断变化的。
- T(n)：语句频度或称时间频度——算法解决问题所执行语句的次数。
- f(n)：辅助函数，使得T(n)/f(n)的极限为不等于零的常数，那么称f(n)是T(n)的同数量级函数。
- O：大 O 符号,一种符号,表示渐进于无穷的行为——大 O 表示只是说有上界但并不是上确界。
「 大 O 符号表示法 」，即 T(n) = O(f(n))
在 大 O 符号表示法中，时间复杂度的公式是： T(n) = O( f(n) )，其中 f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。
假设每行代码的执行时间都是单位 1；那么就可以简化时间复杂度：
// demo1 T(n) = O(2n+1) => T(n) = O(n)
for (let i = 0; i < n; ++i) {
// 1
let temp = i; // n
temp++; // n
}
常数阶 O(1)
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是 O(1)，如：
let i = 0,
j = 1;
j++;
--i;
线性阶 O(n)
如 demo1，for 循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此这类代码都可以 用 O(n)来表示它的时间复杂度。
对数阶 O(logN)
let i = 1;
while (i < n) {
i = i * 3;
}
从上面代码可以看到，在 while 循环里面，每次都将 i 乘以 3，于是就有 3^x >= n => x > log3^n。也就是说 当循环 log3^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)
线性对数阶 O(nlogN)
线性对数阶 O(nlogN) 其实非常容易理解，将时间复杂度为 O(logn)的代码循环 N 遍的话，那么它的时间复杂度 就是 n * O(logN)，也就是了 O(nlogN)。
for (let j = 0; j < n; ++j) {
// 1
let i = 1; // n
let temp = j; // n
temp++; // n
while (i < n) {
i = i * 3;
}
}
平方阶 O(n²)
平方阶 O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。比如冒泡 排序。
立方阶 O(n³)、K 次方阶 O(n^k)
参考上面的 O(n²) 去理解就好了，O(n³)相当于三层 n 循环，其它的类似。
空间复杂度
既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空 间的。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做 S(n)=O(f(n))。 比如直接插入排序的时间复杂度是 O(n^2),空间复杂度是 O(1) 。而一般的递归算法就要有 O(n)的空间复杂度了 ，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量 。
空间复杂度比较常用的有：O(1)、O(n)、O(n²)：
空间复杂度 O(1)
O(1)就是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间 都不变。 哈希算法就是典型的 O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突 的话）。例如冒泡排序
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
空间复杂度 O(n)
function factorial(num) {
if (num === 1) return num;
return num * factorial(num - 1); // 递归求n的阶乘，会递归n次，每次递归内部计算时间是常数，需要保存n个调用记录，复杂度 O(n)
}
const view = factorial(100);
console.time(1);
console.log(view); // 1: 3.568ms
console.timeEnd(1);
空间复杂度 O(n²)
空间复杂度 O(n²) 就是在代码的执行过程中新开辟了一个二维列表，如下面这段 java 代码。
public void array(int n) {
int[][] array = new int[n][n];
for (int i = 1; i <= n; i++) {
for (int j=0;j<n;j++) {
array[i][j] = j;
}
}
}
斐波那契时间复杂度和空间复杂度分析
function Fibonacci(n) {
if (n <= 1) return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
console.time(1);
console.log(Fibonacci(20)); // 10946
console.timeEnd(1); // 1: 4.115966796875ms
// console.time(2)
// console.log(Fibonacci(100))
// console.timeEnd(2) // stack overflow 堆栈溢出
当 n=5 时，在递归调用过程中，Fibonacci(3)被计算了 2 次，Fibonacci(2)被计算了 3 次
，Fibonacci(1)被计算了 5 次，Fibonacci(0)被计算了 3 次。
可见递归出口在 n>=2 是，就会一直在现有函数栈上开辟新的空间，所以容易出现栈溢出。
二叉树的高度为n-1,一个高度为 k 的二叉树最多可以由(2^n-1)个叶子节点，也就是递归过程函数调用的次数，
所以时间复杂度为 O(2^n)，而空间复杂度为 S(n)。
尾递归优化： 空间复杂度可达到 o(1)，但时间复杂度是 o(n)。
function Fibonacci01(n, ac1 = 1, ac2 = 1) {
if (n <= 1) return ac2;
return Fibonacci01(n - 1, ac2, ac1 + ac2);
}
console.time(3);
console.log(Fibonacci01(100)); // 573147844013817200000
console.timeEnd(3); // 3: 0.52197265625ms