算法的复杂度分析
参考来源：
1、《大话数据结构》
2、极客时间-数据结构与算法之美；
1、开场白
算法的重要性不言而喻。
我们先来看一下算法(Algorithm)的定义：
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
这里我将《大话数据结构》里面的定义拿了过来，其实去维基百科上看一下，基本上一次差不多，但是维基上比较复杂。
算法具有五个特点，同时好的算法有四个设计要求：(可能有些课本不同，求同存异。)
五个特点是：
1）输入
2）输出
3）有穷性
4）确定性
5）可行性
四个要求：
1）正确性
2）可读性
3）健壮性
4）时间效率高和存储量低
具体的可以自行查找，接下来我们进入主题，一个好的算法怎么去度量算法的效率？
2、算法效率的度量方法
算法的度量方法可以分为事后统计方法、事前分析估算法。
首先说说这个事后统计方法。
这种方法主要是通过设计号的测试程序和数据，利用计算机计时器对不同算法的程序运行时间进行比较。
其实很容易想到，一个算法都设计好了，怎么度量？当然是前面加个时间，后面加个时间，一减，不就出来了程序跑的时间了。但是，这种方式呢，有一些弊端：
第一，要事后统计，算法得先写出来吧？如果写出来的算法耗时很高，不就白写了？
第二，这个呢，玩游戏的同学肯定很清楚，一个游戏的流畅度受硬件的影响，同一个游戏，跑在最新的硬件上，基本上可以说比几年前机器要流畅。算法也可以这样想，因为处理算法的运算速度受操作系统、编译器、运行框架等等环境的影响。
第三，算法的测试数据设计困难。这个好像不需要过多解释，因为算法的输入不是固定的，所以谁知道会输入什么样的测试数据呢。
根据上面我们可以暂时不选择事后统计方法，要选的话也只是用来测试，毕竟算法编好了，也是需要测试的。千万不要认为事后统计方法没用了，像leetcode上面，提交能够计算出用时等数据，不就是事后统计方法嘛。
接下来我们来重点看一下事前分析估算法。
很好解释，事前就是程序编写之前，依据统计方法对算法进行估算。
经过分析，可以发现一个程序在计算机上运行时所消耗的时间取决于下列因素：
1）算法采用的策略、方法。
2）编译产生的代码质量。
3）问题的输入规模。
4）机器执行指令的速度。
第一条是算法好坏的根本，第二条需要由编译器来支持，第四条要看硬件性能。所以抛开固定环境有关的，我们可以这样看：
一个程序的运行时间，依赖于算法的好坏和问题的输入规模。
我们已经选好了算法效率度量的方法了，接下来我们来看看算法到底是怎么度量效率的？
3、算法的时间复杂度
同样的，先看一下算法时间复杂度的定义
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n));。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。
绕的头都晕了，简而言之：一个算法运行时间(抛开环境的影响),是关于这个算法解决问题规模的函数。规模越大，运行时间或者称时间复杂度越高。
现在基本上都在使用大O记法来表示时间复杂度。
上面的定义了解一下就好了，我们来看看时间复杂度怎么分析：
其实分析时间复杂度，只需要关注循环次数最多的代码块就好了。
时间复杂度有两个法则：加法法则、乘法法则
时间复杂度的加法法则：T(n) = T1(n) + T2(n) = O(f(n1)) + O(f(n2)) = O(MAX(f(n1),f(n2)))。
就是说，当循环代码块是独立的，只需要看时间复杂度高的就行了。
比如：
let O = function(n) {
for(let i = 0; i < n; i++) {
...
}
let j = 1
while (j <= n) {
j *= 2;
}
}
函数O里面包含两个循环，但是两个循环都是独立的，所以时间复杂度是两个循环中最大的一段循环的时间复杂度，这里是O(n),同学们可以想一下，两段循环的事件负责度都是多少。后面会有讲解。
时间复杂度的乘法法则：T(n) = T1(n) * T2(n) = O(f(n1)) * O(f(n2)) = O(f(n1) * f(n2))。
就是说，当循环代码块是嵌套的时候，需要将每个循环的时间复杂度相乘得到总的时间复杂度。
比如：
let O2 = function(n) {
for(let i = 0; i < n; i++) {
let j = 1
while (j <= n) {
j *= 2;
}
}
}
这里的函数O2里面也是包含两个循环，但是两个循环是嵌套在一起的，所以总的时间复杂度就等于，外层循环时间复杂*内存循环时间复杂度。这里的时间复杂度是O(nlogn)。具体每个循环怎么分析等会再说，只需要直到，外层时间复杂度O(n),内层的是O(logn)。
上面是时间复杂度的两个法则，现在我们来看一下几种常见的时间复杂度具体分析。
1）常量阶O(1)
2）对数阶O(logn)
3）线性阶O(n)
4）线性对数阶O(nlogn)
5）平方阶O(n^2)
6）指数阶O(2^n)
7）阶乘阶O(n!)
是不是觉得括号里面的表达式很熟悉？没错，这就是基本初等函数表达式，如果不记得的话可以查看高数上的第一章。
我们都知道，时间复杂度是算法执行时间的增长率。结合上面常见的时间复杂度表示，我们不用看下面也能推出：
O(1) < O(logn) < O(nlogn) < O(n) < O(n^2) < O(2^n) < O(n!)
这是根据函数的图形得出来的，可以尝试画出上述函数的图形，看一下在坐标系中的图形就能直观的感受这个含义。
了解了函数的渐进增长，接下来就一个一个分析下。
1）常数阶：
就是只执行一次的语句。
比如：
function ab() {
let a = 1,b = 2; //执行一次
a += 1; //执行一次
b -= 1; //执行一次
a = a + b; //执行一次
}
上面这个函数，里面有四个执行一次的语句，实际上不管有多少这样语句，它的时间复杂度都是O(1)，而不是O(4)什么的。
因为这些语句与问题的大小无关。这句话后面多看两个例子就懂了。
2）对数阶O(logn)、线性对数阶O(nlogn):
还记得上面那个函数嘛？
let O2 = function(n) {
for(let i = 0; i < n; i++) {
let j = 1
while (j <= n) {
j *= 2;
}
}
}
我们分析一下。外层的先放一下，内层的函数我们拿出来就是：
let j = 1
while (j <= n) {
j *= 2;
}
从代码中可以看出，变量j的值从1开始取，每循环一次就乘以2。当大于n时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量j的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：
2^1 2^2 ... 2^x =n
=> x = log2^n;
如果是 3^1 3^2 3^3 .. 3^x = n
=> x = log3^n
但是我们知道 log3^n = log3^2 * log2^n = O(C * log2^n);
在使用大O表示法的时候，我们可以忽略系数即O(C * f(n)) = O(f(n));
所以 log3^n => O(log2^n)因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。
同时我们来说一下O2这个函数，内层是O(logn);外层是下一步说到的线性阶O(n)；那根据乘法法则，总的时间复杂度是多少？就不需要说了吧。
3）线性阶O(n):
这个很好理解，比如
for(let i = 0; i < n; i++) {
...
}
这个循环就是循环了n次，直到i = n的时候退出循环，时间复杂度就是O(n)。
4）平方阶O(n^2):
一个线性阶是O(n)，根据乘法法则，两个线性阶嵌套在一起不就是O(n * n)嘛。
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
...
}
}
这个就是平方阶O(n^2);
5）O(m + n),O(m * n):
这是拓展的，可以自己写一下时间复杂度是O(m + n),O(m * n)的代码块。
4、算法的空间复杂度
其实空间复杂度比时间复杂度好理解，时间复杂度是算法执行时间与数据规模的增长关系。空间复杂度就是算法的存储空间与数据规模的增长关系。
空间复杂度使用的没有时间复杂度多，因为现在计算机硬件的发展，人们可以更多的拿空间来换取时间。
空间复杂度为O(1):若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称次算法为原地工作，空间复杂度记为O(1)
5、最好、最坏、平均时间复杂度
最好时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
最坏时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
平均时间复杂度：所有情况下，求一个平均值，可以省略掉系数、低阶、常量
平均时间复杂度是所有情况最有意义的，因为它是期望的运行时。
平均时间复杂度计算就是将所有的情况相加 / 运行了多少次情况。这个后面遇到具体的算法会具体分析。
算法的复杂度分析
1、开场白
2、算法效率的度量方法
3、算法的时间复杂度
4、算法的空间复杂度
5、最好、最坏、平均时间复杂度