什么情況下不能使用最壞情況評估算法的復(fù)雜度?

關(guān)注公眾號“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識！

前言

你好，我是彤哥，一個每天爬二十六層樓還不忘讀源碼的硬核男人。

上一節(jié)，我們從最壞、平均、最好三種情況分析了算法的復(fù)雜度，得出結(jié)論，通常來說，使用最壞情況來評估算法的復(fù)雜度完全夠用了。

但是，有些算法是不能使用最壞情況來評估算法的復(fù)雜度的。

那么，有哪些算法呢？

本節(jié)，我們將從動態(tài)數(shù)組以及快速排序這兩個個例入手來分析不能使用最壞情況評估復(fù)雜度的情形。

動態(tài)數(shù)組，對應(yīng)于Java中的ArrayList，在插入元素時，分成兩種情況：

1. 數(shù)組未滿，元素放在size下標(biāo)的位置即可；

2. 數(shù)組滿了，需要擴(kuò)容，一般擴(kuò)容為N倍大小，Java里面是1.5倍，擴(kuò)容時需要創(chuàng)建一個新的數(shù)組，并把原來的元素一個一個地拷貝到新的數(shù)組中，再插入新的元素；

我簡單地寫一段代碼，你可以感受下：

public classDynamicArray{
private int[] array;
private int size;

publicDynamicArray(int capacity){
this.array = new int[capacity];
this.size = 0;
    }

// 插入元素，時間復(fù)雜度為多少呢？
publicvoidadd(int element){
// 判斷是否需要擴(kuò)容
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;
    }

publicstaticvoidmain(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);
        }
    }
}

那么，對于動態(tài)數(shù)組，它的插入元素方法的時間復(fù)雜度是多少呢？

按照上一節(jié)的說法，按照最壞情況來評估，最壞情況是插入元素時正好數(shù)組滿了需要擴(kuò)容的時候，此時，需要創(chuàng)建一個額外的數(shù)組，同時有一個遍歷原數(shù)組的過程。

所以，在最壞情況下，動態(tài)數(shù)組插入元素的時間復(fù)雜度為O(n)。

但是，這樣合理嗎？

顯然是不合理的，我插入前面(n-1)個元素的時候，它的時間復(fù)雜度都是O(1)，就只有插入第n個元素的時候它的時間復(fù)雜度才是O(n)，所以，這樣來評估動態(tài)數(shù)組插入元素的時間復(fù)雜度明顯不合理。

那么，如果我把第n個元素插入所需要的時間均攤到所有元素上會怎么樣呢？

這樣的話，前面每個元素的插入時間只需要加1，變成O(2)，忽略常數(shù)項，就還是O(1)，這樣明顯是要合理一些。

這種方式跟計算平均時間復(fù)雜度有點類似，但是，它不是平均時間復(fù)雜度，它有一個專門的名稱叫做均攤時間復(fù)雜度。

均攤時間復(fù)雜度，即對一批樣本中出現(xiàn)的個例情況，將它們耗費的時間均攤到所有樣本上，算出來的一個時間復(fù)雜度。

你可以把它和平均時間復(fù)雜度對比一下：

1. 平均時間復(fù)雜度的計算中沒有個例，所有樣本是同等看待的，想一下線性查找的過程；

2. 均攤時間復(fù)雜度的計算中有個例，這種個例往往就是最壞的情況，想一下動態(tài)數(shù)組插入元素的過程；

3. 線性查找第n個元素不是個例，不能把它的時間均攤到所有元素上；

這兩個概念嚴(yán)格來說是有區(qū)別的，如果無法理解，當(dāng)成一樣的也問題不大，比如，這里如果按平均時間復(fù)雜度計算的話，結(jié)果為 (1+1+1+...+n)/n = (n-1+n)/n = (2n-1)/n=2-1/n，忽略常數(shù)項和低階項，最終的結(jié)果也是O(1)。

好了，那么，我們再來看一下動態(tài)數(shù)組插入元素時的額外空間復(fù)雜度。

是不是一樣的道理？數(shù)組未滿時額外空間復(fù)雜度為O(1)，數(shù)組滿時額外空間復(fù)雜度為O(n)，均攤一下變成O(1)。

所以，對于動態(tài)數(shù)組插入元素的過程，它的均攤時間復(fù)雜度和均攤額外空間復(fù)雜度都是O(1)。

大家都知道經(jīng)典的快速排序的時間復(fù)雜度是O(nlogn)，那么，它的最壞時間復(fù)雜度是不是也是O(nlogn)呢？

讓我們來看下面這個數(shù)組：

這是一個有序數(shù)組，如果此時用經(jīng)典快速排序來對其進(jìn)行排序會怎樣呢？

我們?nèi)∽钣疫叺脑貫檩S（Pivot），也就是12，將小于12的放在它的左邊，大于12的放在它的右邊，發(fā)現(xiàn)沒有比12大的，所以，右邊沒有元素，經(jīng)過此步，12的位置固定不變了。

接著，將12左右兩邊的元素再各取最右邊的元素為軸，12的右邊沒有元素，所以，只需要處理左邊就可以了，以10為軸，比10小的放在它的左邊，比10大的放在它的右邊，發(fā)現(xiàn)10的右邊也沒有元素（12已經(jīng)固定了），經(jīng)過此步，10的位置固定了。

同樣地，最后一步到1這里，排序完成。

讓我們來分析一下整個過程的復(fù)雜度：

第一步，需要遍歷(n-1)個元素；

第二步，需要遍歷(n-2)個元素；

...

最后一步，需要遍歷0個元素；

這種情況下的時間復(fù)雜度為：(n-1) + (n-2) + ... + 1 + 0 = (n-1)n/2 = n^2/2 - n/2，忽略常數(shù)項和低階項，它的時間復(fù)雜度為O(n^2)。

所以，對于有序數(shù)組，使用經(jīng)典快速排序，它的時間復(fù)雜度為O(n^2)，這也是最壞的情況。

但是，似乎從來沒有人告訴你，經(jīng)典快速排序的時間復(fù)雜度為O(n^2)，而是O(nlog2)，這是為什么呢？

那是因為有序數(shù)組相對于經(jīng)典快速排序，也是屬于個例，窮舉無限多的樣本之后，有序數(shù)組的可能性實在是太小，所以，我們一般說經(jīng)典快速排序的時間復(fù)雜度為O(nlogn)，而不是以最壞情況來評估它的時間復(fù)雜度。

我們這里說的是經(jīng)典快速排序，為什么要加“經(jīng)典”兩個字呢？

好了，本節(jié)，我們通過兩個案例來說明了并不是所有的算法都使用最壞情況來評估它的復(fù)雜度。

到現(xiàn)在為止，我們都是使用的大O來表示算法的復(fù)雜度，但是，在其它書籍中，你可能還見過Θ、Ω等表示法，它們又是什么意思呢？

下一節(jié)，我們接著聊。