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

我們先看一個例子：

/*
 例1：查找x在數(shù)組中出現(xiàn)的位置撩炊，如果沒有找到外永，返回-1。n表示數(shù)組array的長度
*/
int findIndex(int[] array, int n, int x) {
  int i = 0;
  int index = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       index = i;
       //break; //暫時注釋掉此行
    }
  }
  return index;
}

當(dāng)把break語句注釋掉的時候衰抑，總是需要遍歷整個數(shù)組象迎，所以時間復(fù)雜度就是數(shù)組的長度，為O(n)呛踊。
當(dāng)有break語句的時候砾淌，如果找到x，則會提前退出（顯然這種寫法更高效）谭网。
我們知道x可能出現(xiàn)在數(shù)組的任何位置汪厨，可能是第一個（時間復(fù)雜度為O(1)），可能是最后一個（時間復(fù)雜度為O(n)）愉择，也可能不存在數(shù)組中（時間復(fù)雜度為O(n)）劫乱。

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

最好情況時間復(fù)雜度 就是狭吼，在最理想的情況下，執(zhí)行這段代碼的時間復(fù)雜度殖妇。
最壞情況時間復(fù)雜度 就是刁笙，在最糟糕的情況下，執(zhí)行這段代碼的時間復(fù)雜度
最好谦趣、最壞都是在對應(yīng)的都是極端情況下的代碼復(fù)雜度疲吸，發(fā)生的概率其實(shí)并不大。

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

平均時間復(fù)雜是為了更好地表示平均情況下的復(fù)雜度前鹅。
還是上面例1摘悴，結(jié)合概率知識，我們知道舰绘，要查找的變量x在數(shù)組中的位置蹂喻，有 n+1 種情況：在數(shù)組的0～n-1位置中和不在數(shù)組中。
我們暫且認(rèn)為每種情況發(fā)生的概率都一樣為：1/(n+1)除盏。
每種情況的時間復(fù)雜度為:1/(n+1)1叉橱、1/(n+1)2、1/(n+1)3...1/(n+1)n者蠕、1/(n+1)*n
所以平均時間復(fù)雜度為:(所有情況下的時間復(fù)雜度的總和)/(總情況數(shù))，即：

平均時間復(fù)雜度.png

其實(shí)上面的概率并不都是：1/(n+1)杠愧。
要查找的變量 x待榔，要么在數(shù)組里，要么就不在數(shù)組里流济。
我們假設(shè)在數(shù)組中與不在數(shù)組中的概率都為 1/2锐锣。
查找的數(shù)據(jù)出現(xiàn)在 0～n-1，這 n 個位置的概率也是一樣的绳瘟，為 1/n雕憔，則每種情況出現(xiàn)的概率為1/(2n)履婉。
每種情況的時間復(fù)雜度為：1/(2n)1覆享、1/(2n)2俄删、1/(2n)3...1/(2n)n
查找的數(shù)據(jù)不再數(shù)組里，則概率為1/2稍计。時間復(fù)雜度為：1/2*n。
所以平均時間復(fù)雜度為:(所有情況下的時間復(fù)雜度的總和)/(總情況數(shù))匕垫，即：

平均時間復(fù)雜度.png

均攤時間復(fù)雜度

均攤時間復(fù)雜度拜马，聽起來跟平均時間復(fù)雜度有點(diǎn)兒像渗勘。
對于初學(xué)者來說，這兩個概念確實(shí)非常容易弄混俩莽。

/*
 例2:n表示數(shù)組長度旺坠，count表示數(shù)組存儲數(shù)據(jù)的個數(shù)
 往數(shù)組中添加數(shù)據(jù)，如果數(shù)組滿了扮超，則依次打印出來取刃，然后清空數(shù)組
*/
int[] array = new int[n];
int count = 0;
void insert(int val) {
        if (count == array.length) {
            for (int i = 0; i < array.length; ++i) {
                System.out.println(array[i]);
            }
            System.out.println(val);
            array = new int[n];
            count = 0;
        } else {
            array[count] = val;
            count++;
        }
}

分析下前面說的三種時間復(fù)雜度。
最好：最理想的情況下數(shù)組空閑出刷，時間復(fù)雜度為O(1)
最差：數(shù)組恰好不空閑璧疗，時間復(fù)雜度是 O(n)
平均：假設(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ù)雜度.png

那究竟如何使用攤還分析法來分析算法的均攤時間復(fù)雜度呢？
每一次 O(n) 的插入操作种樱，都會跟著 n次 O(1) 的插入操作蒙袍，
所以把耗時多的那次操作均攤到接下來的 n 次耗時少的操作上，均攤下來嫩挤，
這一組連續(xù)的操作的均攤時間復(fù)雜度就是 O(1)害幅。這就是均攤分析的大致思路。

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

小結(jié)

• 同一段代碼蹂午，在不同輸入的情況下栏豺，復(fù)雜度量級有可能是不一樣的。所以有了最好豆胸、最壞奥洼、平均、均攤時間復(fù)雜度晚胡。
• 其中最好灵奖、最壞情況下的時間復(fù)雜度分析起來比較簡單嚼沿。平均、均攤兩個復(fù)雜度分析相對比較復(fù)雜瓷患。
• 在大多數(shù)情況下骡尽，我們并不需要區(qū)分最好、最壞擅编、平均情況時間復(fù)雜度三種情況攀细。很多時候，我們使用一個復(fù)雜度就可以滿足需求了爱态。只有同一塊代碼在不同的情況下谭贪，時間復(fù)雜度有量級的差距，我們才會使用這三種復(fù)雜度表示法來區(qū)分锦担。
• 平均復(fù)雜度只在某些特殊情況下才會用到俭识，而均攤時間復(fù)雜度應(yīng)用的場景比它更加特殊、更加有限吆豹。