数据结构与算法（二）复杂度

吐槽

国庆假期第三天，昨天出去胡吃海喝，和朋友出去逛逛寺庙，然后今天早上又来实验室，给猫猫铲臭臭真的臭死我了，一见我就往我身上冲emmmmmmmmmm，今天就把上周就该写的复杂度分析这块写下，因为这块真的还蛮重要的

//我看的是极客时间上一个老师讲的，就是把他讲的梳理一下

本文思维导图

我觉得复杂度这块主要就是这些，而且分析最多的也是时间复杂度

为什么要有复杂度分析？

这个问题，我之前学的时候重来没想过，写项目的时间重来没想过，好像生活中自己处理事情的时候也没怎么去想自己处理事情的方法所耗费的时间和资源

但是我之前刷ACM题的时候，有几次明明自己写的算法是正确的，但是网站判定的结果就是错误的，要么是时间超了，要么是空间超了，同样的一道题，不同人用的方法不一样，就是结果虽然可能一样，但是别人的算法就是没有超时，或者比自己的所耗费的时间少emmmmmm，这里就是涉及到复杂度的问题了。

但是这块复杂度又如何去算啊？

好像有方法，就是把代码跑一遍，然后看下时间，看下消耗的空间，这样好像也可以唉，但是仔细想下，这个方法很矛盾。

因为我不可能每次写个算法就都重新跑一遍，然后看下时间和空间emmmm这样有点傻，但是意思可以的

这个方法有两个很大的局限性：

1. 测试结果非常依赖测试环境
   
   这个很明显啊，我拿个高处理器的电脑去处理同一段代码，和拿个低处理器的处理，肯定高处理器的在其他条件相同的情况下的时候，它处理的时间快啊


2. 测试结果受数据规模的影响很大
   
   就好比排序算法一样，数据规模大小很影响排序算法的性能

说了这么多，我们到底需要什么样的分析算法的方式

• 简单，明了，能在代码运行之前看出来//肯定不是很精确的


• 不和测试机器环境有关


• 不受测试规模影响

大O复杂度表示法

大O表示法：称一个函数g(n)是O(f(n))，当且仅当存在常数c>0和n0>=1，对一切n>n0均有|g(n)|<=c|f(n)|成立，也称函数g(n)以f(n)为界或者称g(n)受限于f(n)。记作g(n)=O(f(n))。 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。

这个就是百度百科上面的定义，but看这个概念一般人还真的是搞不懂什么意思，反正我当时学的时候也不知道这个是什么鬼意思。但是其实这个概念理解起来也是蛮简单的

因为我们要看代码的执行效率，所以我们要看代码的执行时间和占的空间//占的空间这里简单的小规模算法先不考虑

所以，我们在乎的代码执行的时间，但是我们又如何估算呢？

先看下这个代码

int text(int n){
int sum = 0; //1
int i，n; //2
for (i = 0; i sum += i; //4
}
return sum;
}


我们看下上面这个代码块，一共就执行的就4个重要代码，每段代码块就类似操作，尽管不一样，但是按照现在cpu执行的那么高速的样子，其实每个代码都只执行一点点时间，所以我们认为他们运行的时间都是一样的，记成一Time

现在上面的代码，第1个标记，第2个标记，分别执行了一个Time,然后第3个标记和第4个标记的位置的，是分别执行一个n*Time的时间

所以，总的来说，这段代码运行时间就是（2n+2)*Time，随着n的增大而增大

我们设代码执行的总时间为T(n）

所以，T（n) = （2n+2）*Time 代码执行时间和n成正比

所以，代码执行时间和每行代码的执行的次数成正比

综上所述，大O表示法就出来了

T(n) = O(f(n))

上面公式的个个含义：

• T(n)表示代码的总的总的执行时间


• n表示数据规模的大小


• f(n)表示每行代码的执行次数和


• 公式中的O表示正比的意思

要注意的点：大O时间复杂度并不是代码的具体执行时间，只是一种趋势，一种变化的趋势

当n特别特别大的时候，可以忽略不记常数项对这个的影响，我们上面代码里面，T（n) = （2n+2）Time 展开时候发现T(n) = 2Time+2nTime，当n为无穷大的时候

其实最后的结果就是：T(n) = O(n)

分析时间复杂度的三个原则

关注法则：只关心执行次数最大的那段代码

因为我们上面也看到了，大O就是一种变化趋势，那些计算的常量什么的其实都不重要，因为当n无穷大的时候，其他的常量，低价，系数什么的其实都没什么作用，所以，我们分析一段代码的时候，只需要看他循环次数最多的地方

int text(int n){
int sum = 0; //1
int i，n; //2
for (i = 0; i sum += i; //4
}
return sum;
}


我们继续看这个例子，这段代码就是只是关心下，执行次数最多的那给循环，其他的地方都无关紧要

加法法则：总的复杂度等于量级最大的那段

先看下下面的代码

int text(int n){
int sum1 = 0;
int sum2 = 0;
int sum3 = 0;
int i,j;
//1
for (i = 0; i <100;i++){
sum1 += i;
}
for(i = 0;i sum2 += i;
}
//3
for (i = 0;i for (j = 0;j sum3 += i;
}
}
return sum1+sum2+sum3;
}


我们再进行分析

第一段代码，就是执行了100次，所以这个就是个常量时间，和n无关

//就是能明显知道执行次数是具体数字的时候，这个常量就不能省略

第二段代码，时间复杂度就是O(n)

第三段代码，时间复杂度就是O(n*n)

然后我们要求这段总的代码的时间复杂度的时候，还是比较下，选最大的那一段，因为还是那句话，把n当成无穷大时候，就可以比较了

所以，这段代码的时间复杂度是O(n*n)

乘法法则：嵌套的复杂度等于里外复杂度的乘积

这个也好理解啊，冒泡就是典型的例子，但是我们还是看下下面的例子

int f(int n){
int sum = 0;
int i;
for(i = 0;i sum += i;
}
return sum;
}
int ff(int n){
int s = 0;
int i;
for(i = 0;i s = s + f(i);
}
return s;
}


这个代码也是很简单，就是一个代码里面调用另一个的函数

所以总的复杂度就是

T(n) = T(n1) * T（n2) = O（n*n)

几种常见的复杂度分析

• 常量阶


• 对数阶


• 线性阶


• 线性对数阶


• k方阶


• 指数阶


• 阶乘阶

下面举例子说明

O(1) 常数阶

O(1)不是只是执行了一行代码的意思，它只是表示时间复杂度

int i = 1；
int j = 2;
int sum = i + j;


这个整体有3行代码，但是还是O(1)的时间复杂度

只要代码的执行时间不随着n的增大而增大，就是O(1),一般情况下，就是算法中没有循环，递归这些的

O(logn)、O(nlogn）

这块高中数学要学好哇哇哇，对数这块都忘完了

看下下面的代码

int i = 1;
while (i <= n){
i = i * 2;
}


我们要求这块的时间复杂度就发行很尴尬，不知道要求多少次

一步一步分析，当变量i从1开始取的时候，每次循环都是乘以2，当它大于n的时候，循环结束

然后我们分析下i的变量的取值 2 ，22 ，222 , 22…

也就是2的阶乘

当2的x次方大于n的时候，就循环结束

所以 x = log2 n

所以，这个代码的时间复杂度就是O(log2 n)

然后我们在记对数的时候，通常忽略系数

所以，复杂度统一为O(lngn)

再利用乘法法则，像什么快排的时间复杂度就是O(nlong n)

O（m+n）,O(m*n)

这块就是代码里面有两个数据规模，不是一个n了，所以这块要看下


int text(int m ,int n){
int sum1 = 0;
int sum2 = 0;

int i = 1;
for(i = 0; i sum1 += i;
}

for (i = 0; i sum2 += i;
}
return sum1 + sum2;
}


之前我们说的加法法则是看最大的那块，但是我们现在不知道那块最大，m，n都可以无穷大判定下，所以没办法比较，因此，这块的时间复杂度就是O(m+n)

乘法法则类似的套路

最好、最坏，平均，均摊情况时间复杂度

我们看了时间复杂度这块的概念和大O的表示方法，为什么还有有这四种情况呢，因为传入的数据可能会影响到最后的结果

很明显的例子就是排序算法

先看下一个例子

就是一个简单的从数组中找个数，看它在不在

int find(int []array,int n,int x){
int i = 0;
int pos = -1;
for (i = 0; i if (array[i] == x){
pos = i;
break;
}
}
return pos;
}


这块的分析也就尴尬了，因为我们发现这块程序结束的条件就是找到这个数就结束，或者找不到返回-1，遍历的过程次数不确定

当如果我们要找的数在第一个的时候，找到了，直接break了，那么时间复杂度就是O(1)

如果都找完了还是没找到，这个时候复杂度就是O(n)，所以，不同情况下，这段代码的时间复杂度也是不同的

所以，引进了最好、最坏，平均，均摊情况时间复杂度的概念

最好时间复杂度

在最最理想的情况下，执行这段代码的时间复杂度，这块很好理解，比如我算法就是要找元素，第一个就是，所以，执行一次就找到了

最坏时间复杂度

在最最最坏的情况下，执行这段代码的复杂度，还是上面的例子，很简单，就是我找数组还是没找到，这就是最坏的情况

平均时间复杂度

在代码中心所有情况的次数加权平均表示

均摊时间复杂度

在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

总结

下次分析时间复杂度的时候，自己也要分析下各种情况