淺析最好，最壞，平均，均攤時間復(fù)雜度

今天我會繼續(xù)給你講四個復(fù)雜度分析方面的知識點(diǎn)，最好情況時間復(fù)雜度（best case time complexity）、最壞情況時間復(fù)雜度（worst case time complexity）、平均情況時間復(fù)雜度（average case time complexity）、均攤時間復(fù)雜度（amortized time complexity）。如果這幾個概念你都能掌握，那對你來說，復(fù)雜度分析這部分內(nèi)容就沒什么大問題了。

最好、最壞情況時間復(fù)雜度

上一節(jié)我舉的分析復(fù)雜度的例子都很簡單，今天我們來看一個稍微復(fù)雜的。你可以用我上節(jié)教你的分析技巧，自己先試著分析一下這段代碼的時間復(fù)雜度。

// n 表示數(shù)組 array 的長度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) pos = i;
  }
  return pos;
}

你應(yīng)該可以看出來，這段代碼要實(shí)現(xiàn)的功能是，在一個無序的數(shù)組（array）中，查找變量 x 出現(xiàn)的位置。如果沒有找到，就返回 -1。按照上節(jié)課講的分析方法，這段代碼的復(fù)雜度是 O(n)，其中，n 代表數(shù)組的長度。

我們在數(shù)組中查找一個數(shù)據(jù)，并不需要每次都把整個數(shù)組都遍歷一遍，因?yàn)橛锌赡苤型菊业骄涂梢蕴崆敖Y(jié)束循環(huán)了。但是，這段代碼寫得不夠高效。我們可以這樣優(yōu)化一下這段查找代碼。

// n 表示數(shù)組 array 的長度
int find(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;
}

這個時候，問題就來了。我們優(yōu)化完之后，這段代碼的時間復(fù)雜度還是 O(n) 嗎？很顯然，咱們上一節(jié)講的分析方法，解決不了這個問題。

因?yàn)?，要查找的變?x 可能出現(xiàn)在數(shù)組的任意位置。如果數(shù)組中第一個元素正好是要查找的變量 x，那就不需要繼續(xù)遍歷剩下的 n-1 個數(shù)據(jù)了，那時間復(fù)雜度就是 O(1)。但如果數(shù)組中不存在變量 x，那我們就需要把整個數(shù)組都遍歷一遍，時間復(fù)雜度就成了 O(n)。所以，不同的情況下，這段代碼的時間復(fù)雜度是不一樣的。

為了表示代碼在不同情況下的不同時間復(fù)雜度，我們需要引入三個概念：最好情況時間復(fù)雜度、最壞情況時間復(fù)雜度和平均情況時間復(fù)雜度。

顧名思義，最好情況時間復(fù)雜度就是，在最理想的情況下，執(zhí)行這段代碼的時間復(fù)雜度。就像我們剛剛講到的，在最理想的情況下，要查找的變量 x 正好是數(shù)組的第一個元素，這個時候?qū)?yīng)的時間復(fù)雜度就是最好情況時間復(fù)雜度。

同理，最壞情況時間復(fù)雜度就是，在最糟糕的情況下，執(zhí)行這段代碼的時間復(fù)雜度。就像剛舉的那個例子，如果數(shù)組中沒有要查找的變量 x，我們需要把整個數(shù)組都遍歷一遍才行，所以這種最糟糕情況下對應(yīng)的時間復(fù)雜度就是最壞情況時間復(fù)雜度。

平均情況時間復(fù)雜度

我們都知道，最好情況時間復(fù)雜度和最壞情況時間復(fù)雜度對應(yīng)的都是極端情況下的代碼復(fù)雜度，發(fā)生的概率其實(shí)并不大。為了更好地表示平均情況下的復(fù)雜度，我們需要引入另一個概念：平均情況時間復(fù)雜度，后面我簡稱為平均時間復(fù)雜度。

平均時間復(fù)雜度又該怎么分析呢？我還是借助剛才查找變量 x 的例子來給你解釋。

要查找的變量 x 在數(shù)組中的位置，有 n+1 種情況：在數(shù)組的 0～n-1 位置中和不在數(shù)組中。我們把每種情況下，查找需要遍歷的元素個數(shù)累加起來，然后再除以 n+1，就可以得到需要遍歷的元素個數(shù)的平均值，即：

平均情況

我們知道，時間復(fù)雜度的大 O 標(biāo)記法中，可以省略掉系數(shù)、低階、常量，所以，咱們把剛剛這個公式簡化之后，得到的平均時間復(fù)雜度就是 O(n)。

這個結(jié)論雖然是正確的，但是計(jì)算過程稍微有點(diǎn)兒問題。究竟是什么問題呢？我們剛講的這 n+1 種情況，出現(xiàn)的概率并不是一樣的。我?guī)憔唧w分析一下。（這里要稍微用到一點(diǎn)兒概率論的知識，不過非常簡單，你不用擔(dān)心。）

我們知道，要查找的變量 x，要么在數(shù)組里，要么就不在數(shù)組里。這兩種情況對應(yīng)的概率統(tǒng)計(jì)起來很麻煩，為了方便你理解，我們假設(shè)在數(shù)組中與不在數(shù)組中的概率都為 1/2。另外，要查找的數(shù)據(jù)出現(xiàn)在 0～n-1 這 n 個位置的概率也是一樣的，為 1/n。所以，根據(jù)概率乘法法則，要查找的數(shù)據(jù)出現(xiàn)在 0～n-1 中任意位置的概率就是 1/(2n)。

因此，前面的推導(dǎo)過程中存在的最大問題就是，沒有將各種情況發(fā)生的概率考慮進(jìn)去。如果我們把每種情況發(fā)生的概率也考慮進(jìn)去，那平均時間復(fù)雜度的計(jì)算過程就變成了這樣

推導(dǎo)過程

這個值就是概率論中的加權(quán)平均值，也叫作期望值，所以平均時間復(fù)雜度的全稱應(yīng)該叫加權(quán)平均時間復(fù)雜度或者期望時間復(fù)雜度。

引入概率之后，前面那段代碼的加權(quán)平均值為 (3n+1)/4。用大 O 表示法來表示，去掉系數(shù)和常量，這段代碼的加權(quán)平均時間復(fù)雜度仍然是 O(n)。

你可能會說，平均時間復(fù)雜度分析好復(fù)雜啊，還要涉及概率論的知識。實(shí)際上，在大多數(shù)情況下，我們并不需要區(qū)分最好、最壞、平均情況時間復(fù)雜度三種情況。像我們上一節(jié)課舉的那些例子那樣，很多時候，我們使用一個復(fù)雜度就可以滿足需求了。只有同一塊代碼在不同的情況下，時間復(fù)雜度有量級的差距，我們才會使用這三種復(fù)雜度表示法來區(qū)分。

均攤時間復(fù)雜度

到此為止，你應(yīng)該已經(jīng)掌握了算法復(fù)雜度分析的大部分內(nèi)容了。下面我要給你講一個更加高級的概念，均攤時間復(fù)雜度，以及它對應(yīng)的分析方法，攤還分析（或者叫平攤分析）。

均攤時間復(fù)雜度，聽起來跟平均時間復(fù)雜度有點(diǎn)兒像。對于初學(xué)者來說，這兩個概念確實(shí)非常容易弄混。我前面說了，大部分情況下，我們并不需要區(qū)分最好、最壞、平均三種復(fù)雜度。平均復(fù)雜度只在某些特殊情況下才會用到，而均攤時間復(fù)雜度應(yīng)用的場景比它更加特殊、更加有限。

老規(guī)矩，我還是借助一個具體的例子來幫助你理解。（當(dāng)然，這個例子只是我為了方便講解想出來的，實(shí)際上沒人會這么寫。）

// array 表示一個長度為 n 的數(shù)組
 // 代碼中的 array.length 就等于 n
 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; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

我先來解釋一下這段代碼。這段代碼實(shí)現(xiàn)了一個往數(shù)組中插入數(shù)據(jù)的功能。當(dāng)數(shù)組滿了之后，也就是代碼中的 count == array.length 時，我們用 for 循環(huán)遍歷數(shù)組求和，并清空數(shù)組，將求和之后的 sum 值放到數(shù)組的第一個位置，然后再將新的數(shù)據(jù)插入。但如果數(shù)組一開始就有空閑空間，則直接將數(shù)據(jù)插入數(shù)組。

那這段代碼的時間復(fù)雜度是多少呢？你可以先用我們剛講到的三種時間復(fù)雜度的分析方法來分析一下。

最理想的情況下，數(shù)組中有空閑空間，我們只需要將數(shù)據(jù)插入到數(shù)組下標(biāo)為 count 的位置就可以了，所以最好情況時間復(fù)雜度為 O(1)。最壞的情況下，數(shù)組中沒有空閑空間了，我們需要先做一次數(shù)組的遍歷求和，然后再將數(shù)據(jù)插入，所以最壞情況時間復(fù)雜度為 O(n)。

那平均時間復(fù)雜度是多少呢？答案是 O(1)。我們還是可以通過前面講的概率論的方法來分析。

假設(shè)數(shù)組的長度是 n，根據(jù)數(shù)據(jù)插入的位置的不同，我們可以分為 n 種情況，每種情況的時間復(fù)雜度是 O(1)。除此之外，還有一種“額外”的情況，就是在數(shù)組沒有空閑空間時插入一個數(shù)據(jù)，這個時候的時間復(fù)雜度是 O(n)。而且，這 n+1 種情況發(fā)生的概率一樣，都是 1/(n+1)。所以，根據(jù)加權(quán)平均的計(jì)算方法，我們求得的平均時間復(fù)雜度就是：

平均時間復(fù)雜度

至此為止，前面的最好、最壞、平均時間復(fù)雜度的計(jì)算，理解起來應(yīng)該都沒有問題。但是這個例子里的平均復(fù)雜度分析其實(shí)并不需要這么復(fù)雜，不需要引入概率論的知識。這是為什么呢？我們先來對比一下這個 insert() 的例子和前面那個 find() 的例子，你就會發(fā)現(xiàn)這兩者有很大差別。

首先，find() 函數(shù)在極端情況下，復(fù)雜度才為 O(1)。但 insert() 在大部分情況下，時間復(fù)雜度都為 O(1)。只有個別情況下，復(fù)雜度才比較高，為 O(n)。這是 insert()第一個區(qū)別于 find() 的地方。

我們再來看第二個不同的地方。對于 insert() 函數(shù)來說，O(1) 時間復(fù)雜度的插入和 O(n) 時間復(fù)雜度的插入，出現(xiàn)的頻率是非常有規(guī)律的，而且有一定的前后時序關(guān)系，一般都是一個 O(n) 插入之后，緊跟著 n-1 個 O(1) 的插入操作，循環(huán)往復(fù)。

所以，針對這樣一種特殊場景的復(fù)雜度分析，我們并不需要像之前講平均復(fù)雜度分析方法那樣，找出所有的輸入情況及相應(yīng)的發(fā)生概率，然后再計(jì)算加權(quán)平均值。

針對這種特殊的場景，我們引入了一種更加簡單的分析方法：攤還分析法，通過攤還分析得到的時間復(fù)雜度我們起了一個名字，叫均攤時間復(fù)雜度.
那究竟如何使用攤還分析法來分析算法的均攤時間復(fù)雜度呢？

我們還是繼續(xù)看在數(shù)組中插入數(shù)據(jù)的這個例子。每一次 O(n) 的插入操作，都會跟著 n-1 次 O(1) 的插入操作，所以把耗時多的那次操作均攤到接下來的 n-1 次耗時少的操作上，均攤下來，這一組連續(xù)的操作的均攤時間復(fù)雜度就是 O(1)。這就是均攤分析的大致思路。你都理解了嗎？

均攤時間復(fù)雜度和攤還分析應(yīng)用場景比較特殊，所以我們并不會經(jīng)常用到。為了方便你理解、記憶，我這里簡單總結(jié)一下它們的應(yīng)用場景。如果你遇到了，知道是怎么回事兒就行了。

對一個數(shù)據(jù)結(jié)構(gòu)進(jìn)行一組連續(xù)操作中，大部分情況下時間復(fù)雜度都很低，只有個別情況下時間復(fù)雜度比較高，而且這些操作之間存在前后連貫的時序關(guān)系，這個時候，我們就可以將這一組操作放在一塊兒分析，看是否能將較高時間復(fù)雜度那次操作的耗時，平攤到其他那些時間復(fù)雜度比較低的操作上。而且，在能夠應(yīng)用均攤時間復(fù)雜度分析的場合，一般均攤時間復(fù)雜度就等于最好情況時間復(fù)雜度。

盡管很多數(shù)據(jù)結(jié)構(gòu)和算法書籍都花了很大力氣來區(qū)分平均時間復(fù)雜度和均攤時間復(fù)雜度，但其實(shí)我個人認(rèn)為，均攤時間復(fù)雜度就是一種特殊的平均時間復(fù)雜度，我們沒必要花太多精力去區(qū)分它們。你最應(yīng)該掌握的是它的分析方法，攤還分析。至于分析出來的結(jié)果是叫平均還是叫均攤，這只是個說法，并不重要。

內(nèi)容小結(jié)

今天我們學(xué)習(xí)了幾個復(fù)雜度分析相關(guān)的概念，分別有：最好情況時間復(fù)雜度、最壞情況時間復(fù)雜度、平均情況時間復(fù)雜度、均攤時間復(fù)雜度。之所以引入這幾個復(fù)雜度概念，是因?yàn)?，同一段代碼，在不同輸入的情況下，復(fù)雜度量級有可能是不一樣的。

在引入這幾個概念之后，我們可以更加全面地表示一段代碼的執(zhí)行效率。而且，這幾個概念理解起來都不難。最好、最壞情況下的時間復(fù)雜度分析起來比較簡單，但平均、均攤兩個復(fù)雜度分析相對比較復(fù)雜。如果你覺得理解得還不是很深入，不用擔(dān)心，在后續(xù)具體的數(shù)據(jù)結(jié)構(gòu)和算法學(xué)習(xí)中，我們可以繼續(xù)慢慢實(shí)踐！

課后思考

我們今天學(xué)的幾個復(fù)雜度分析方法，你都掌握了嗎？你可以用今天學(xué)習(xí)的知識，來分析一下下面這個 add() 函數(shù)的時間復(fù)雜度。

int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往數(shù)組中添加一個元素
void add(int element) {
   if (i >= len) { // 數(shù)組空間不夠了
     // 重新申請一個 2 倍大小的數(shù)組空間
     int new_array[] = new int[len*2];
     // 把原來 array 數(shù)組中的數(shù)據(jù)依次 copy 到 new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array 復(fù)制給 array，array 現(xiàn)在大小就是 2 倍 len 了
     array = new_array;
     len = 2 * len;
   }
   // 將 element 放到下標(biāo)為 i 的位置，下標(biāo) i 加一
   array[i] = element;
   ++i;
}