背景
对于日常开发，算法基本用不到太多，那要不要学习算法呢？如果要学习，那如何学习算法？
要不要？
1. 帮助自己深入了解框架，库，提高自身实力
2. 帮助自己提高处理问题难度的高度
3. 钱多多
如何学？
从时间复杂度和空间复杂度开始
问题
1. 什么是时间复杂度，空间复杂度, 时间频度/语句频度？
2. 为什么需要复杂度分析？直接机器运行不香吗？
定义
通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，第二部就是分析算法的时间复杂度。
算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。
1. 事后统计的方法 （正确，但是局限）
1-1. 要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行
1-2. 测试的结果依赖测试的环境
例如： 测试环境中硬件的不同会对测试结果有很大的影响。比如，我们拿同样一段代码，分别用 Intel Core i9 处理器和 Intel Core i3 处理器来运行，不用说，i9 处理器要比 i3 处理器执行的速度快很多。还有，比如原本在这台机器上 a 代码执行的速度比 b 代码要快，等我们换到另一台机器上时，可能会有截然相反的结果。
1-3. 测试结果受数据规模的影响很大
例如： 如果测试数据规模太小，测试结果可能无法真实地反映算法的性能。比如，对于小规模的数据排序，插入排序可能反倒会比快速排序要快！2. 事前分析估算的方法 （不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法）
一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
(1). 算法采用的策略、方法；
(2). 编译产生的代码质量；
(3). 问题的输入规模；
(4). 机器执行指令的速度。
一个算法是由控制结构（顺序、分支（选择）和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。时间复杂度
在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
例如，如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3)。
为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。
相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为 T(n) ，定义为任何大小的输入 n 所需的最大运行时间。另一种较少使用的方法是平均情况复杂度，通常有特别指定才会使用。时间复杂度可以用函数 T(n) 的自然特性加以分类，
举例来说，有着 T(n) = O(n) 的算法被称作“线性时间算法”；而 T(n) = O(Mn) 和 Mn= O(T(n)) ，其中 M ≥ n > 1 的算法被称作“指数时间算法”。空间复杂度
The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely.[1]Similar to time complexity, space complexity is often expressed asymptotically in big O notation.
算法或计算机程序的空间复杂度是作为输入特征函数解决计算问题实例所需的内存空间量。它是算法在完全执行之前所需的内存。[1]与时间复杂度类似，空间复杂度通常用大O表示法来表示。大O符号
又称为渐进符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。大O代表“order of ...”（……阶）。
时间复杂度
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)：表示每行代码执行的次数总和
O：表示代码的执行时间 T(n) 与 f(n) 表达式成正比
当 n 很大时，例如 10000，甚至更大，T(n) = O(f(n)) 可以表示为 T(n) = O(n) 。这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。function fun1(n) {
let sum = 0;
for(let i=0; i <= n; i++) {
sum += i;
}
return sum
}
function fun2(n) {
let sum = 0, sum1 = 0;
for(let i=0; i <= n; i++) { // 循环1
sum += i;
}
for(let i = 0; i <= n; i++) { // 循环2
for(let j = 0; j <= n; j++) {
sum += i * j;
}
}
return sum
}
function fun3(n) {
let sum = 0, i = 0;
for(; i <= n; i++) {
sum += fun1(i);
}
return sum
}
fun1 中第1行都是常量，对 n 的影响不大，所以总的时间复杂度要看第2、3行的循环，即时间复杂度为：O(n) 。
fun2 中循环1的时间复杂度为 O(n) ，循环2的时间复杂度为 O(n2)，当 n 趋于无穷大时，总体的时间复杂度要趋于 O(n2) ，即上面代码的时间复杂度是 O(n2)。
fun3 的时间复杂度是 O(n * T(fun1)) = O(n*n) ，即 O(n2) 。
所以：T(c+n)=O(n)，T(m+n)=O(max(m, n))，T(n) = T1(n) T2(m) = O(nm)，其中 c 为常量
空间复杂度
时间复杂度表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度表示算法的存储空间与数据规模之间的增长关系。例如：
function fun(n) {
let a = [];
for (let i = 0; i < n; i++) {
a.push(i);
}
return a;
}
以上代码我们可以清晰的看出代码执行的空间为 S(1+n) = O(n)，即为 i 及数组 a 占用的储存空间。
扩展
最好时间复杂度：在最理想的情况下，执行这段代码的时间复杂度 （Ω（大欧米茄）符号）
最坏时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度 （O（大 O）符号）
平均时间复杂度：所有情况下，求一个平均值，可以省略掉系数、低阶、常量 （Θ (Big-Theta) 表示法）
均摊时间复杂度：一种特殊的平均时间复杂度
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
参考
1.https://blog.csdn.net/zolalad/article/details/11848739
2. https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
3.https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7
4.https://livecodestream.dev/post/complete-guide-to-understanding-time-and-space-complexity-of-algorithms/
5.https://mp.weixin.qq.com/s?__biz=MzUzNjk5MTE1OQ==&mid=2247484204&idx=1&sn=3433b9191b67ac9b09452b0d6e3a0639&chksm=faec87f4cd9b0ee213f03f451069f4c5fd352cf0c573d043c1819760ef1085a4457af99605a8&scene=21#wechat_redirect
6.https://www.cnblogs.com/54chensongxia/p/14012838.html
7. https://www.cnblogs.com/onepixel/articles/7674659.html#3%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8Finsertion-sort
