我们都知道，数据结构和算法本身解决的就是"快"和"省"的问题，如何让代码更省存储空间，如果让代码运行的更快，所以执行效率是算法一个非常重要的考量指标。所以这里我讨论一下时间、空间复杂度分析。
为什么要分析复杂度？
虽然我们把代码跑一遍，利用统计、监控，这种事后统计法可以得到很准确的算法执行时间和占用内存的大小，但是这种统计方法会存在一些局限性。
- 测试的结果会受测试环境影响
- 测试结果受测试数据规模所影响
所以，才需要一个可以粗略估算计算法的执行效率的方法，也是接下来的时间、空间复杂度分析方法。
大O表示法
粗略来说，算法的执行效率就是算法代码的执行时间。 通过下面的代码来估算下这段代码的执行时间
function call(n){
let sum = 0;
for(let i=1;i<=n;i++){
sum +=i
}
return sum;
}
复制代码从代码从上到下的角度看，以上代码执行的步骤读取数据-数据运算-返回数据。
每行每次执行的时间是不一样的，这里由于是粗略的估算，所以每行代码执行的时间看做是一样的，都为one_time，在这个假设之下，我们这段代码的总执行时间T(n)就是：第2行的执行时间是1个one_time，第3、4行的执行时间分别都是n*one_time，所以总执行时间为T(n) = (2n+1) * one_time。可以看出来，执行时间与每行代码的执行次数成正比。
接下来，我们在看下面的代码
function call(n){
let sum = 0;
for(let i=1;i<=n;i++){
let k=1;
for(;k<=n;k++){
sum = sum + i*k
}
}
return sum;
}
复制代码上面的例子中，第2行代码执行时间为1个one_time,第3行、4行执行时间都是n * one_time，第5、6行的执行循环了n²遍，所以需要n²*one_time的执行时间，所以，整段代码的执行时间就是(2n+2n²+1)*one_time。
虽然我们不知道具体的one_time值是多少，但是通过这两段代码的执行时间推导过程，我们可以很清楚的知道所有代码的执行时间T(n) 与每行代码的执行次数成正比。
经常上面的规律，总结出了下面这样一个公司，也就是大O。
T(n) = O(f(n))
上面的公式中，T(n)表示总的执行时间，n表示数据的规模大小，f(n)表示每行代码的执行的次数总和。因为是个公式，所以用f(n)表示。O表示代码的执行时间T(n)和代码执行次数f(n)成正比。
所以前面的2个例子，T(n) = O(2n+1)，T(n) = O(2n+2n²+1)，这就是大O时间复杂度表示法。
大O时间复杂度实际上并不是具体表示代码真正执行的时间，而是表示代码执行时间随着数据规模越大而增长的变化趋势。所以也称为渐进时间复杂度。
因公式中的系数、常量、低阶三部分并不会影响增长趋势，所以无论n有多大，1000、10000，都可以忽略。我们只需记住一个最大量就可以了。前面2个例子，用大O表示法就可以记成：T(n) = O(n)、T(n) = O(n²)
时间复杂度分析方法
1. 只需关注循环执行次数最多的代码
因为大O表示法，只是表示一种变化趋势，所以我们通常会忽略公式中的低阶、常量、系数，只需要关注一个最大阶的量级就可以了。我们在分析一个算法、一段代码的时间复杂度时，也只关注循环执行次数最多那段代码就可以了。
依旧拿前面的例子来说
function call(n){
let sum = 0;
for(let i=1;i<=n;i++){
sum +=i
}
return sum;
}
复制代码第2行是常量级的执行时间，与n的大小无关，所以对复杂度没有什么影响，第3、4行是这段代码执行次数最多的，所以要重点分析，前面也说过，这2行代码被执行了n次，所以就是总的时间复杂度就是O(n)。
function call(n){
let sum = 0;
for(let i=1;i<=n;i++){
let k=1;
for(;k<=n;k++){
sum = sum + i*k
}
}
return sum;
}
复制代码同理，这里执行次数最多的是第5、6行，都执行了n²遍，所以这段代码的执行时间就是O(n²)。
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
function call(n){
let sum = 0;
for(let u=0;u<=100;u++){
sum = sum+u
}
let sum2 = 0;
for(let u=0;p<=n;p++){
sum2 = p+sum2
}
let sum3 = 0;
for(let i=1;i<=n;i++){
let k=1;
for(;k<=n;k++){
sum3 = sum3 + i*k
}
}
return sum + sum2 + sum3;
}
复制代码这里，第一段代码执行了100次，所以是一个常量的执行时间，和n的规模无关。
所以，只要是一个已知的数，跟n无关，哪怕是1000，100000那也是常量级的执行时间。当n无限大的时候就可以忽略掉。随便对代码的执行时间会有很大影响，但我们这里所说的是时间复杂度的概念。它表示一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，都可以忽略。因为它本身不会对增长趋势有什么影响。
第二段代码的时间复杂度是O(n)，第三代代码时间复杂度是O(n²)。
这三段代码中，我们取最大的量级，所以整段代码的时间复杂度就是O(n²)。也就是总的时间复杂度就等于量级最大的那段代码的时间复杂度。
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
function call(n){
let num = 0;
for(let i=0;i<n;i++){
num = num + f(i);
}
}
function f(n){
let sum = 0;
for(let i=0;i<n;i++){
sum = sum+i;
}
return sum;
}
复制代码单独看call()函数，如果f()函数只是一个普通的操作，则3、4行的是件复杂度就是 T(n) = O(n)。但很明显f()不是一个普通的操作，f()的时间复杂度是 T(n) = O(n)，所以call()函数的时间复杂度就是T(n) = O(n) * O(n) = O(n²)。
几种常见的时间复杂度分析
虽然代码千差万别，但是常见的复杂度量级并不多，这里有多项式量级和非多项式量级2种。
** 非多项量级**只有2个：O(2n) 和 O(n!)
当数据n规模越来越大时，非多项量级算法的执行时间会急剧增加，求解问题的时间会无限增长，所以，当非多项式时间复杂度的算法其实是非常低效的算法。
这里，我们主要关注下几种常见的多项式时间复杂度
1. O(1)
O(1)只是常量级时间复杂度的一种表示方式，并不是单纯的指一行代码，只要代码的执行时间不会随着n的增大而增长，这些的代码我们就标记为O(1)。例如下面的这段代码
let a = 0;
let b = 3;
let c = 4;
let d = a+b*4;
复制代码即便这里有4行代码，但是因为都是常量级，它的时间复杂度就是O(1)而不是O(4)，通常来讲只要算法中不存在 循环、递归即使有成千上万的代码，它的时间复杂度也是O(1)。
2. O(logn)、O(nlogn)
对数阶时间复杂度是非常常见的，同时也是很难分析的一种时间复杂度
let i=1;
while (i <= n) {
i = i * 2;
}
复制代码前面我们说的时间复杂度分析方法，第三行代码是循环次数最多的。所以，我们只需计算这段代码执行了多少次，就可以知道它的时间复杂度是多少。
代码中，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。变量 i 的取值就好比是一个等比数列。逐个列出来就是这样的：
O(log2 n )
在看看，修改之后的是多少呢？
let i=1;
while (i <= n) {
i = i * 3;
}
复制代码经过刚刚的思路，可以很明显看出来，这段代码的时间复杂度是：O(log3 n)。
实际上，不管是以2打底，还是以3打底亦或者是以10打底，我们都可以把所有对数阶的时间复杂度记为 O(logn)。因为对数之间是可以相互转换的，而且基于我们前面的理论得知,在采用大O标记复杂度的时候，可以忽略系数，因此，在对数阶时间复杂度的表示方法里，我们忽略所有的低，统一表示为O(logn)。
理解了O(logn)，对于O(nlogn)就好理解了，在一段代码的时间复杂度是O(logn)的时候，我们循环执行 n 遍，时间复杂度就是O(nlogn)。O(nlogn)也是一种常见的算法时间复杂度。比如，归并排序，快速排序的时间复杂度都是O(nlogn)。
3. O(m+n) 、O(m*n) 代码的复杂由2个数据的规模来决定的。
function call(m,n) {
int sum_1 = 0;
for (let i=1; i < m; ++i) {
sum_1 = sum_1 + i;
}
let sum_2 = 0;
for (let j=1; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
复制代码从代码中可以看出来，m 和 n 分别表示2个数据规模，所以我们无法评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单的利用加法法则，去省略掉一个。所以，上面的时间复杂度就是O(m+n)，但乘法的法则是不变的，依旧是O(m*n)。
空间复杂度分析
理解了时间复杂度分析，那空间复杂度分析就相对于很简单了。
前面说过，时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
function fn( n) {
let i = 0;
let a = [];
for (i; i <n; ++i) {
a[i] = i * i;
}
}
复制代码和时间复杂度分析一样，忽略掉常量级，每次数组赋值都会申请一个空间存储变量，所以这段代码的空间复杂度是O(n)。
常见的空间复杂度就是O(1)、O(n)、O(n²)，像O(logn)、O(nlogn)这样的对数阶复杂度平时都是用不到的。
总结
复杂度也叫渐进复杂度，分为时间复杂度和空间复杂度，(一个表示执行时间的快慢，一个表示内存消耗的大小)用来分析算法执行效率与数据规模之间的增长关系，可以忽略的表示，越高阶复杂度的算法，执行效率越低。 常用的复杂度并不多，从高到底的分别是O(1)、O(logn)、O(n)、O(nlogn)、O(n²)。
