最好、最壞情況時間複雜度
// n表示數組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;
}
這段代碼要實作的功能是，在一個無序的數組（array）中，查找變量 x 出現的位置。如果沒有找到，就傳回 -1。按照上節課講的分析方法，這段代碼的複雜度是 O ( n ) O(n) O(n)，其中，n 代表數組的長度。
我們在數組中查找一個資料，并不需要每次都把整個數組都周遊一遍，因為有可能中途找到就可以提前結束循環了。但是，這段代碼寫得不夠高效。我們可以這樣優化一下這段查找代碼。
// n表示數組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;
}
這個時候，問題就來了。我們優化完之後，這段代碼的時間複雜度還是 O(n) 嗎？
要查找的變量 x 可能出現在數組的任意位置。如果數組中第一個元素正好是要查找的變量 x，那就不需要繼續周遊剩下的 n-1 個資料了，那時間複雜度就是 O(1)。但如果數組中不存在變量 x，那我們就需要把整個數組都周遊一遍，時間複雜度就成了 O(n)。是以，不同的情況下，這段代碼的時間複雜度是不一樣的。
為了表示代碼在不同情況下的不同時間複雜度，我們需要引入三個概念：最好情況時間複雜度、最壞情況時間複雜度和平均情況時間複雜度。
最好情況時間複雜度
在最理想的情況下，執行這段代碼的時間複雜度。就像我們剛剛講到的，在最理想的情況下，要查找的變量 x 正好是數組的第一個元素，這個時候對應的時間複雜度就是最好情況時間複雜度。
最壞情況時間複雜度
在最糟糕的情況下，執行這段代碼的時間複雜度。就像剛舉的那個例子，如果數組中沒有要查找的變量 x，我們需要把整個數組都周遊一遍才行，是以這種最糟糕情況下對應的時間複雜度就是最壞情況時間複雜度。
平均情況時間複雜度
好情況時間複雜度和最壞情況時間複雜度對應的都是極端情況下的代碼複雜度，發生的機率其實并不大。為了更好地表示平均情況下的複雜度，我們需要引入另一個概念：平均情況時間複雜度，後面簡稱為平均時間複雜度。
要查找的變量 x 在數組中的位置，有 n+1 種情況：在數組的 0～n-1 位置中和不在數組中。我們把每種情況下，查找需要周遊的元素個數累加起來，然後再除以 n+1，就可以得到需要周遊的元素個數的平均值，即：
我們知道，時間複雜度的大 O 标記法中，可以省略掉系數、低階、常量，是以，咱們把剛剛這個公式簡化之後，得到的平均時間複雜度就是 O(n)。
這個結論雖然是正确的，但是計算過程稍微有點兒問題。究竟是什麼問題呢？我們剛講的這 n+1 種情況，出現的機率并不是一樣的。
我們知道，要查找的變量 x，要麼在數組裡，要麼就不在數組裡。這兩種情況對應的機率統計起來很麻煩，為了友善你了解，我們假設在數組中與不在數組中的機率都為 1/2。另外，要查找的資料出現在 0～n-1 這 n 個位置的機率也是一樣的，為 1/n。是以，根據機率乘法法則，要查找的資料出現在 0～n-1 中任意位置的機率就是 1/(2n)。
是以，前面的推導過程中存在的最大問題就是，沒有将各種情況發生的機率考慮進去。如果我們把每種情況發生的機率也考慮進去，那平均時間複雜度的計算過程就變成了這樣：
這個值就是機率論中的權重平均值，也叫作期望值，是以平均時間複雜度的全稱應該叫權重平均時間複雜度或者期望時間複雜度。
引入機率之後，前面那段代碼的權重平均值為 (3n+1)/4。用大 O 表示法來表示，去掉系數和常量，這段代碼的權重平均時間複雜度仍然是 O(n)。
轉自《資料結構與算法之美》