数据结构与算法学习笔记一：复杂度分析
一、为什么要进行复杂度分析
数据结构是用来解决“快”和“省”的问题，也就是如何是代码运行更快以及如何节省更多的空间。因此执行效率在算法中就是一个非常重要的考核指标。时间、空间复杂度分析就是用来衡量一个算法代码的执行效率的指标。复杂度分析在数据结构和算法中占有核心的地位，你每使用一个数据结构和算法，都需要进行时间、空间复杂度分析，以确定最优方案。
在日常的测试和生产中，我们可以把代码执行一遍，通过各种统计和监控也能分析出代码的执行效率以及资源消耗，比如性能测试，也可以很直观的看到代码的执行效率。这种称作“事后统计法”。但是这种方法有一些局限性。
1.测试结果非常依赖测试环境
一段算法代码在不同的机器和硬件上执行效率是不同的，可能一段代码在A机器上跑出了惊人的效果，等到到了B机器上，结果反而不如人意。因为程序运行在环境上，不同环境产生了不同的结果。
2.测试结果受数据规模的影响
对于比如排序之类的算法来说，测试结果受数据规模影响较大，比如完全有序的数据，不需要进行交换就完成了排序。而完全无序或者逆序的数据，就需要进行大量的比较交换来完成一次排序。因此某一个测试结果并不能完全代表该算法的执行效率。
综合上边两点，我们需要一种不需要通过“事后统计法”并且可以直观的粗略分析出算法的执行效率的方法，也就是时间、空间复杂度分析法。
二、大O复杂度表示法
算法的执行效率，粗略的来说就是代表算法的执行时间。看下边的一段代码：
public int LeiJia(int n){
int sum = 0;
for(int i=1;i<=n;i++){
sum = sum+i;
}
return sum;
}上边的方法用来求1+2+3+...+n的和，从CPU的角度来看，我们假设每行代码执行时间是相同的，不考虑其它如资源消耗等情况，因此假设每一行代码的执行时间是相同的，为time，在这个假设的基础上，第2行执行时间就是time，第3、4行都执行了n次，所以这两行的执行时间就是2n*time，那么这段代码的总执行时间就是（2n+1）time，可以看出总的执行时间T（n）与代码执行的次数成正比。再看如下代码段：
public int sum(int n){
int sum = 0;
int i =1;
int j =1;
for(;i<=n;++i){
j=1;
for(;j<=n;++j){
sum = sum +i*j;
}
}
return sum;
}如上代码段使用了两个for循环，假设条件与上边相同，每一行的执行时间仍相同为time，那么对于2、3、4行代码，他们的执行时间都为time，5、6行代码执行了n次，所以他们的总时间为2n*time，而7、8行代码执行了n²次，所以他们的总时间为2n²*time，那么这段代码的总执行时间就是3time+2n*time+2n²*time，也就是说T(n) = （3+2n+2n²）*time。
如上两个代码段的分析，尽管我们并不知道time的具体时间，但是可以推断出一个重要的规律就是所有代码的执行时间T(n)与每行代码的执行次数n成正比，这个规律总结成公式就是：
T(n)= O(f(n))
在这个公式中，T(n) 就是代码的执行时间，n表示数据规模，f(n)表示每行代码的执行次数总和，公式中的O，用来表示他们的比例关系，也就是代码的执行时间T(n)与代码的总执行次数成正比。总结上述两个代码段，第一个代码段中的T(n)=O(2n+1)，第二个代码段中T(n)=O(2n²+2n+3)。这就是大O时间复杂度表示法。大O时间复杂度表示法并不是代表代码真正的执行时间，而是表示代码执行时间随数据规模的变化关系。所以也称作渐进时间复杂度，简称时间复杂度。随着n的规模不断扩大，在上述公式中的低阶、常量、系数三部分并不会影响执行时间，比如n和n²，当n等于1时二者相同，当n等于100的时候二者相差好几个数量级。因此在使用大O时间复杂度表示法的时候，我们可以忽略上述三部分，仅保留最高阶的量级即可。因此上述两个代码段的时间复杂度可以表示为T(n) = O(n) 和T(n) = O(n²)。
三、时间复杂度分析
上个章节中对大O时间复杂度分析做了阐述，这个章节看一下如何在具体的算法中准确的分析出时间复杂度。
1.只关注执行次数最多的一段代码
如前文说到，低阶、常量、系数都会随数据规模的增大而变的无关紧要因此被忽略。那么在实际分析时间复杂度的时候，我们便可忽略这部分内容而直接去看代码中执行次数最多的一段代码。如上述示例一中，执行最多的就是for循环那部分执行了n次，因此它的时间复杂度就是O(n)，示例二中执行最多的是嵌套内部的for循环，它执行了n²次，因此复杂度为O(n²)。
2.加法法则：总复杂度等于量级最大的那段代码的复杂度
这个原则与上述原则实际相同，也就是在推倒开始到最后结果的过程，还是示例一种，第二行执行了一次，时间复杂度是O(1）常数级别，后边的代码时间复杂度是O(n)，加一起之后取最大的就是O(n)。示例二也如此，可推出是O(n²)。
3.乘法法则：嵌套的代码段时间复杂度等于嵌套内外代码复杂度的乘积
在示例二中，嵌套了一个代码段，外层代码时间复杂度O(n)，内层代码时间复杂度O(n)，但是外层每执行1次，内层就要执行n次，因此最后的时间复杂度等于二者的乘积O(n²)。
四、几种常见时间复杂度实例分析
虽然算法有很多种，但是常见的时间复杂度量级并不多，按照量级可以分为两种，一种是多项式量级：
常量阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶(Onlogn)、平方阶O(n²)、立方阶O(n³)....k次方阶O(n^k)
另一种是非多项式量级：
指数阶O(2^n)、阶乘阶O(n!)
对于非多项式量级，随着执行次数增长，执行时间会急剧增加，因此暂不讨论这种情况。主要看多项式量级的几种复杂度。
1.O(1)
O(1)并不是表示只执行了一行代码，而只是常量级用来表示时间复杂度的方式。即便如下三行代码的代码段，他的时间复杂度也是O(1)而不是O(3)，O(1)时间复杂度常用于代码的执行时间不会随执行次数n线性增长的代码段。通俗来说就是代码中不存在复杂的逻辑结构，如循环、递归等。
int a = 9;
int b = 1;
int sum = a+b;2.O(logn)、O(nlogn)
对数阶复杂度比较常见，也相对复杂，看如下代码：
public void sum(int n){
int i=1;
while(i<n){
i = i*2;
}
}根据前边的分析，我们只需要看while循环的复杂度就可以了。从代码中可以看出，变量i从1开始，每一次循环就乘以2，直到大于或等于n的时候结束，因此变量i的值实际上就是一个形如2^0 2^1 2^2......2^x = n的等比数列，只要求出x的值就知道这段代码的执行次数了。2^x = n 数学计算x = log2n，所以如上代码的时间复杂度为O(log2n)，那么如上代码如果变成i = i*3呢？时间复杂度就变成了O(log3n)，在数学计算中，log3n等于log3^2 * log2n，因为log3^2是常数，所以可以忽略，因此log3n=log2n，为了方便起见，不管底数是什么，统一记做成logn，也就是上述两种情况的时间复杂度都为O(logn)，对于O(nlogn)就比较好理解了，而根据乘法法则，在O(logn)外层嵌套了一个O(n)复杂度的循环，如for，那么这段代码的时间复杂度就是O(nlogn)
3.O(m+n)、O(m*n)
前边讲过了加法法则和乘法法则，有如下代码段：
public void sum(int m,int n){
int sum = 0;
for(int i =0;i<m;i++){
sum++;
}
for(int j=0;j<n;j++){
sum++;
}
}对于第一个循环，时间复杂度为O(m)，第二个for循环时间复杂度则为O(n)，根据加法法则，二者相加之后时间复杂度为O(m+n)
再看另一个代码段：
public void sum(int m,int n){
int sum = 0;
for(int i =0;i<m;i++){
for(int j=0;j<n;j++){
sum++;
}
}
}对于第一个for循环，时间复杂度为O(m)，第二个for循环时间复杂度为O(n)，因为是嵌套关系，所以根据乘法法则，这段代码的时间复杂度为O(m*n)
对于第一种情况，因为不确定m和n的大小关系，因此无法像n+1一样把常数省略。
五、空间复杂度分析
如上的学习都是针对大O时间复杂度分析，时间复杂度表示算法的执行时间与数据规模的关系，类比一下空间复杂度就是算法的空间占用与数据规模的关系。有如下代码段：
public void print(int n){
int i =0;
int[] a = new int[n];
for(;i<n;i++){
a[i] = i;
}
for(i=n-1;i>=0;i--){
System.out.println(a[i]);
}
}空间复杂度分析的是存储使用情况，因此无需分析执行时间，但是分析方式相同。第二行代码中，我们申请了一个空间存储变量，他是常量阶的，因此跟数据规模没有关系。再看第三行代码，申请了长度为n的数组空间，因此它的空间复杂度为O(n)，而后边的代码都没有用到空间申请，因此这个代码段的空间复杂度就是O(n)
常用的空间复杂度就是O(1)、O(n)、O（n²），对数阶复杂度一般情况下是用不到的。
六、最好、最坏、平均情况时间复杂度
在一些算法的特殊情况下，比如查找、排序，有时并不需要完整的执行完n次代码。那么就一定有两种极端的情况，也就是最好和最坏的情况，同时还存在一个中庸的情况，就是平均时间复杂度。分析如下代码：
public int getX(int array[],int n,int x){
int i = 0;
int pos = -1;
for(;i<n;++i){
if(array[i] == x){
pos = i;
}
}
return pos;
}上述代码实现的功能是从指定数组中查找指定值的下标，不存在就返回-1，根据前边的分析，我们很容易得到这段代码的时间复杂度为O(n)，但是实际在查找过程中，我们可能第一个循环就找到了，那么继续后边的循环就显得没有必要了，因此需要对循环进行有效的控制，如下：
public int getX(int array[],int n,int x){
int i = 0;
int pos = -1;
for(;i<n;++i){
if(array[i] == x){
pos = i;
break;
}
}
return pos;
}上述代码进行了改造，在查找到指定的内容之后，结束循环，也就是说，可能循环并没有执行n次。那么这时候复杂度如何分析呢？显然之前的O(n)是不准确的。这时就要引入新的三个概念，最好、最坏、平均时间复杂度。
最好时间复杂度：顾名思义就是最好的，最理想的情况，就像刚才说的那样，可能在第一次查找的时候就找到了指定元素，然后返回下标。因此上述代码段最好时间复杂度为O(1)
最坏时间复杂度：同上，最坏的就是最不理想、最差的情况下，那就是把整个数组遍历一遍咯。因此上述代码段最坏时间复杂度为O(n)
平均时间复杂度：对于最好和最坏的，都是极端情况下才会出现，实际出现的概率比较小，因此平均时间复杂度更有说服力。
对于上述例子，查找变量x在数组中的例子，有n+1种可能出现的情况，即在数组下标0~n-1和不在数组中的情况。那么我们把每一种情况要遍历的数据个数累加起来然后再除以n+1就得到了需要遍历的元素平均值。即1+2+3+...+ n+n/n+1=n(n+3)/2(n+1)
上述公式简化去掉常量、系数之后得到了平均时间复杂度就是O(n)。这种分析方式忽略了概率的问题，对于x初心在数组中和不出现在数组中的概率各位1/2，那么x落在某个下标的概率就是1/2n，因此加入出现概率之后重新统计需要遍历的平均次数。1*1/2n+2*1/2n+....n*1/2n+n*1/2=3n+1/4，这个值在概率论中称作加权平均值或者期望值，所以平均时间复杂度也可以叫做加权平均时间复杂度或者是期望时间复杂度。加入概率之后，这段代码的时间复杂度简化之后仍为O(n)。
在日常分析中，并不需要过多的去分析算法的最好、最坏和平均时间复杂度，只需要知道时间复杂度即可，只有在算法因特殊原因会产生量级的差距，比如前边的O(1)和O(n)时，才会去考虑。
七、均摊时间复杂度
均摊时间复杂度与平均时间复杂度类似，采用均摊分析法，上节说到，在极少情况下会考虑最好、最坏以及平均时间复杂度，而均摊时间复杂度的应用场景更加特殊以及少见。分析如下代码段：
int [] array = new int[n];
int count = 0;
public void insert(int val){
if(count == array.length){
int sum = 0;
for(int i =0;i<array.length;i++){
sum+=array[i];
}
array[0]=sum;
count=1;
}
array[count] = val;
++count;
}上述代码段实现了一个数组插入的功能，当数组插满了，也就是count==array.length之后，我们使用for循环遍历数组求和，然后清空数组（将下标移到第一个），并将求和之后的值放在数组的第一个位置。然后再将新的数据插入，如果数组中开始就有空闲的位置，则可以直接插入。
在这段代码中，最理想的情况就是数组开始就有空位，那么时间复杂度就是O(1)，最坏的情况就是数组满了的情况，需要遍历求和然后再插入，这时的时间复杂度是O(n)。然后通过之前的计算方式，计算平均时间复杂度，对于数组没有满的情况下，在任意位置插入的时间复杂度都是O(1)，对于特殊情况，数组满了的情况，插入的时间复杂度是O(n)，再看他们出现的概率都是相同的，也就是1/(n+1)，所以平均时间复杂度就是1*1/n+1+1*1/n+1+...+n*1/n+1=O(1)，因此上边这段代码段的平均时间复杂度就是O(1)。但是实际这个例子中，计算平均时间复杂度的时候并不需要引入概率的问题，与前一个代码段相比，这段代码几乎所有的时间复杂度都是O(1)，而前边的代码段只有极特殊的情况下才是O(1)，对于上述代码段，时间复杂度的分部很均匀，出现一个O(n)之后即数组满了之后，会接着出现n-1个O(1)的时间复杂度。针对这种特殊的场景，引入了新的概念，均摊时间复杂度，同时它的分析法叫做均摊分析法。
那么如何均摊呢？所谓均摊法，就是在特殊情况下复杂度为O(n)，而大多数情况都为O(1)的时候，把O(n)均摊给其它情况，均摊下来时间复杂度就是O(1)了，这就是均摊法的大体思路。均摊时间复杂度的出现情况极其少见，一般只有在时间复杂度出现较为规律，并且大多数情况复杂度都很低，只有个别情况下时间复杂度很高的情况才会出现。
八、总结
算法的执行效率用大O时间复杂度表示，常用的时间复杂度按小到大分为O(1)、O(logn)、O(n)、O(nlogn)、O(n²)几种。时间复杂度分析时可以根据加法法则、乘法法则、嵌套乘积法则来分析。在一些场景中会用到最好、最坏、平均、均摊时间复杂度。
本笔记学习内容总结自：