复杂度分析

如何分析、统计算法的执行效率和资源消耗？

为什么需要复杂度分析？

测试结果非常依赖测试环境

1. 同样一段代码，用不同的处理器，执行时间不同
2. 不同的代码在不同的机器上运行，执行时间不同

测试结果受数据规模的影响很大

1. 测试数据规模太小，测试结果无法真实的反应算法的性能。
2. 需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率，这就需要复杂度分析。

大O复杂度表示法

 int cal(int n) {int sum = 0;int i = 1;for (; i <= n; ++i) {sum = sum + i;}return sum;}

• 如下代码表示1到n的累加和，估算这段代码的执行时间。
• CPU的角度看，每行代码都执行类似的操作：读数据-运算-写数据。
• 假设每行代码执行的时间相同，都是unit_time，所以这段代码的执行时间就是(2n+2)*unit_time。
• 所有代码的执行时间T(n)与每行代码的执行次数成正比。

所有代码的执行时间T(n)与每行代码的执行次数n成正比

• T(n)代表代码执行的时间
• n表示数据规模的大小
• f(n)代表每行代码执行的次数总和
• 大O时间复杂度实际上并不具体表示代码真正执行的时间
• 表示代码执行时间随数据规模增长的变化趋势，也称渐进时间复杂度，简称时间复杂度
• 当n很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，都可以忽略

时间复杂度分析

只关注循环次数最多的一段代码

大O这种复杂度只是表示一种变化趋势。所以，我们在分析一个算法，一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的n的量级，就是整段要分析代码的时间复杂度。

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

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

int cal(int n){int ret = 0;int i = 1;for(;i<=n;++i){ret = ret+f(i);}
}
inf f(int n){int sum = 0;int i=1;for(;i<=n;++i){sum = sum+1;}return sum;
}

我们可以把乘法法则看成是嵌套循环。

几种常见的复杂度分析实例

• 多项式量级
  • 常量阶O(1)
  • 对数阶O(logn)
  • 线性阶O(n)
  • 线性对数阶O(nlogn)
  • 平方阶O(n^2) 立方阶O(n^3) k次方阶O(n^k)
• 非多项式量级
  • 指数阶O(2^n)
  • 阶乘阶O(n!)

1.O(1)

O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。如下代码，即便有3行，时间复杂度也是O(1)，而不是O(3)

int i = 8;
int j = 10;
int sum - i+j;

一般情况下，只要算法中不存在循环语句、递归语句，即便有成千上万行的代码，其时间复杂度也为O(1)

2.O(logn) O(nlogn)

对数时间复杂度非常常见，同时也是最难分析的一种时间复杂度。举例如下：

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

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于n时，循环结束。实际上变量i的取值就是一个等比数列

所以这段代码的时间复杂度就是O(log2n)，通过换底公式，我们忽略对数的“底”，统一表示为O(logn)，根据乘法法则，可以很容易理解O(nlogn)，比如归并排序、快速排序的时间复杂度都是O(nlogn)

3.O(m+n)、O(m*n)

代码的复杂度由两个数据的规模来决定，代码如下：

int cal(int m,int n){int sum_1 = 0;int i = 1;for(;i<m;++i){sum_1 = sum_1+i;}int sum_2 = 0;int j = 1;for(;j<n;++j){sum_2 = sum_2+j;}return sum_1+sum_2;
}

m和n表示两个数据规模，我们事先无法评论m和n谁的量级大，所以我们在表示复杂度的时候，就不能简单的用加法法则，省略掉其中一个。所以上面代码的时间复杂度就是O(m+n)。但是乘法法则继续有效。

空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。 类比一下，空间复杂度就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

void pring(){int i = 0;int[] a = new int[n];for(;i<n;++i){a[i] = i*i;}for(i=n-1;i>=0;--i){print out a[j];}
}

第二行代码中，我们申请了一个空间存储变量i，但是它是常量级别的，跟数据规模n没有关系，所以可以忽略。第三行申请了一个大小为n的int类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是O(n)

常见复杂度

思考

有人说，我们项目之前都会进行性能测试，再做代码的时间、空间复杂度分析，是不是多此一举呢？每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？你怎么看待这个问题？

1. 渐进时间、空间复杂度分析为我们提供了一个很好的理论分析方向，并且它是宿主平台无关的，能够让我们对我们程序或算法有一个大致的认识，让我们知道，比如在最坏下程序的执行效率如何，同时也为我们提供了一个不错的桥梁，我们可以说，算法1的时间复杂度是O(n)，算法2的时间复杂度为O(logN)，这样我们立刻就对不同的算法有了一个“效率”上的感性认识。
2. 渐进时间、空间复杂度分析只是一个理论模型，只能提供给粗略的估计分析，我们不能直接断定就觉得O(logN)的算法一定优于O(n),针对不同的宿主环境，不同的数据集，不同的数据量的大小，在实际应用上面可能真正的性能会不同，个人觉得，针对不同的实际情况，进而进行一定的性能基准测试是很有必要的，比如在统一一批手机上(同样的硬件，系统等等)进行横向基准测试，进而选择适合特定应用场景下的最有算法。
3. 渐进式时间，空间复杂度分析与性能基准测试并不冲突，而是相辅相成的，但是一个低阶的时间复杂度程序有极大的可能性会优于一个高阶的时间复杂度程序，所以在实际编程中，时刻关心理论时间，空间度模型是有助于产出效率高的程序的，同时，因为渐进式时间，空间复杂度分析只是提供一个粗略的分析模型，因此也不会浪费太多时间，重点在于在编程时，要具有这种复杂度分析的思维。

最好最坏时间复杂度

//n表示array数组的大小
int find(int[] array,int n,int x){int i = 0;int pos = -1;for(int i=0;i<n;++i){if(array[i] == x){pos = i;}}return pos;
}

你应该可以看出来，这段代码要实现的功能是，在一个无序的数组（array）中，查找变量x出现的位置。如果没有找到，就返回-1。这段代码的时间复杂度为O(n)，我们在寻找的过程中如果提前找到了，可以提前结束，所以可以优化

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

那么问题就来了，优化后的代码时间复杂度还是O(n)吗？

1. 如果数组中的第一个元素刚好是要查找的变量x，那就不需要继续遍历剩下的n-1个数据了，时间复杂度就是O(1)
2. 如果数组中不存在变量x，那我们就需要把整个数组都遍历一遍，时间复杂度就变成O(n)

不同情况下，这段代码的时间复杂度是不一样的。
所以需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度。
最好：最理想情况下，执行这段代码的时间复杂度。
最坏：最糟糕的情况下，执行这段代码的时间复杂度。

平均情况时间复杂度

• 最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的复杂度，我们需要引入另一个概念：平均情况时间复杂度，后面我简称为平均时间复杂度。
• 要查找的变量x在数组中的位置，有n+1种情况：在数组的0~n-1个位置和不在数组中。每种情况下，查找需要遍历的元素个数累加起来，然后再除以n+1，就可以得到需要遍历的元素个数的平均值。

平均时间复杂度为O(n)

这个结论是正确的，但是计算过程稍微有点问题，因为这n+1中情况，出现的概率并不是一样的。

假设在数组中与不在数组中的概率都为1/2，另外0_{n-1之间的概率一样，为1/n，所以根据概率乘法法则，要查找的数据出现在0}n-1中任意位置的概率就是1/(2n)。

所以将每种情况发生的概率也考虑进去，那平均时间复杂度的计算过程就变成了这样：

这个值就是概率论中的加权平均，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度和期望时间复杂度。

均摊时间复杂度

均摊时间复杂度对应的分析方法，摊还分析（或者叫平摊分析）。

均摊时间复杂度应用的场景更加特殊，更加有限。

int[] array = new int[n];
int count = 0;void insert(int val){if(count == array.length){int sum = 0;for(int i=0;i<array.length;++1){sum = sum+1;}array[0] = sum;count = 1;}array[count] = val;++count;
}

• 最好情况时间复杂度O(1)
• 最坏情况下，数组中没有空闲空间，需要先做一遍数组的遍历求和，然后将数据插入，所以最坏情况时间复杂度为O(n)
• 平均时间复杂度为O(1)

概率论方法分析：
假设数组长度为n，可以分为n种情况，每种情况的时间复杂度为O(1)，除此之外还有一种额外的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度为O(n)。而且这n中情况发生的概率是一样的，都是1/(n+1)，所以根据加权平均的计算方法，所以平均时间复杂度为：

如何使用摊还分析来分析均摊时间复杂度呢？

每一次O(n)的插入操作，都会跟着n-1次O(1)的插入操作，所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1)。这就是均摊分析的大致思路。

均摊时间复杂度就是一种特殊的平均时间复杂度。

思考

int[] array = new int[10];
int len = 10;
int i = 0;void add(int element){if(i>= len){int[] new_array = new int[len*2];for(int j=0;j<len;++j){new_array[j] = array[j]; }array = new_array;len = len*2;}array[i] = element;++i;
}

• 最好：O(1)
• 最坏：O(n)
• 平均：O(1)
• 均摊：O(1)