你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。
上一节，我们从最坏、平均、最好三种情况分析了算法的复杂度，得出结论，通常来说，使用最坏情况来评估算法的复杂度完全够用了。
但是，有些算法是不能使用最坏情况来评估算法的复杂度的。
那么，有哪些算法呢？
本节，我们将从动态数组以及快速排序这两个个例入手来分析不能使用最坏情况评估复杂度的情形。
动态数组动态数组，对应于Java中的ArrayList，在插入元素时，分成两种情况：
数组未满，元素放在size下标的位置即可；
数组满了，需要扩容，一般扩容为N倍大小，Java里面是1.5倍，扩容时需要创建一个新的数组，并把原来的元素一个一个地拷贝到新的数组中，再插入新的元素；
我简单地写一段代码，你可以感受下：
public class DynamicArray { private int[] array; private int size; public DynamicArray(int capacity) { this.array = new int[capacity]; this.size = 0; } // 插入元素，时间复杂度为多少呢？ public void add(int element) { // 判断是否需要扩容 if (size >= array.length) { int newCapacity = array.length + (array.length >> 1); int[] newArray = new int[newCapacity]; for (int i = 0; i < array.length; i++) { newArray[i] = array[i]; } this.array = newArray; } array[size++] = element; } public int[] getArray() { return array; } public static void main(String[] args) { DynamicArray dynamicArray = new DynamicArray(4); dynamicArray.add(1); dynamicArray.add(2); dynamicArray.add(3); dynamicArray.add(4); dynamicArray.add(5); dynamicArray.add(6); for (int element : dynamicArray.getArray()) { System.out.println(element); } } }那么，对于动态数组，它的插入元素方法的时间复杂度是多少呢？
按照上一节的说法，按照最坏情况来评估，最坏情况是插入元素时正好数组满了需要扩容的时候，此时，需要创建一个额外的数组，同时有一个遍历原数组的过程。
所以，在最坏情况下，动态数组插入元素的时间复杂度为O(n)。
但是，这样合理吗？
显然是不合理的，我插入前面(n-1)个元素的时候，它的时间复杂度都是O(1)，就只有插入第n个元素的时候它的时间复杂度才是O(n)，所以，这样来评估动态数组插入元素的时间复杂度明显不合理。
那么，如果我把第n个元素插入所需要的时间均摊到所有元素上会怎么样呢？
这样的话，前面每个元素的插入时间只需要加1，变成O(2)，忽略常数项，就还是O(1)，这样明显是要合理一些。
这种方式跟计算平均时间复杂度有点类似，但是，它不是平均时间复杂度，它有一个专门的名称叫做均摊时间复杂度。
均摊时间复杂度，即对一批样本中出现的个例情况，将它们耗费的时间均摊到所有样本上，算出来的一个时间复杂度。
你可以把它和平均时间复杂度对比一下：
平均时间复杂度的计算中没有个例，所有样本是同等看待的，想一下线性查找的过程；
均摊时间复杂度的计算中有个例，这种个例往往就是最坏的情况，想一下动态数组插入元素的过程；
线性查找第n个元素不是个例，不能把它的时间均摊到所有元素上；
这两个概念严格来说是有区别的，如果无法理解，当成一样的也问题不大，比如，这里如果按平均时间复杂度计算的话，结果为 (1+1+1+...+n)/n = (n-1+n)/n = (2n-1)/n=2-1/n，忽略常数项和低阶项，最终的结果也是O(1)。
好了，那么，我们再来看一下动态数组插入元素时的额外空间复杂度。
是不是一样的道理？数组未满时额外空间复杂度为O(1)，数组满时额外空间复杂度为O(n)，均摊一下变成O(1)。
所以，对于动态数组插入元素的过程，它的均摊时间复杂度和均摊额外空间复杂度都是O(1)。
快速排序大家都知道经典的快速排序的时间复杂度是O(nlogn)，那么，它的最坏时间复杂度是不是也是O(nlogn)呢？
让我们来看下面这个数组：
这是一个有序数组，如果此时用经典快速排序来对其进行排序会怎样呢？
我们取最右边的元素为轴（Pivot），也就是12，将小于12的放在它的左边，大于12的放在它的右边，发现没有比12大的，所以，右边没有元素，经过此步，12的位置固定不变了。