0.序言
這篇文章講解三個復雜度分析方面的知識點：
- 最好情況時間復雜度
- 最壞情況時間復雜度
- 平均情況時間復雜度
如果你對簡單的復雜度分析還不了解比藻，建議點擊跳轉閱讀這兩篇文章：
① http://www.reibang.com/p/2d5e5f1bc77e
② http://www.reibang.com/p/4c8fa84a9393
1. 最好、最壞時間復雜度
// 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;
}
這段代碼要是實現(xiàn)的功能是：在一個無序的數(shù)組中伊履，查找變量x出現(xiàn)的位置韩容。如果沒有找到，就返回-1唐瀑。如果數(shù)組中第一個元素正好是要查找的變量x群凶，那就不需要繼續(xù)遍歷剩下的n-1個數(shù)據(jù)了，時間復雜度就是O(1)哄辣。如果數(shù)組中不存在變量x请梢，就需要把整個數(shù)組遍歷一遍，時間復雜度就成了O(n)力穗。所以在不同的情況下毅弧，這段代碼的時間復雜度不一樣。
為了表示代碼在不同情況下的不同時間復雜度当窗，需要引入三個概念
- 最好情況時間復雜度
顧名思義：指的是在最理想的情況下够坐，執(zhí)行這段代碼的時間復雜度。對應以上例子：要查找的變量x崖面，正好是數(shù)組的第一個元素元咙。這個時候對應的時間復雜度就是最好情況時間復雜度。 - 最壞情況時間復雜度
顧名思義：指的是在最糟糕的情況下巫员，執(zhí)行這段代碼的時間復雜度庶香。對應以上例子：要查找變量x，但數(shù)組中沒有變量x简识，需要把整個數(shù)組都遍歷一遍赶掖。這個時候對應的時間復雜度就是最壞情況時間復雜度感猛。 - 平均情況時間復雜度
請看下一小節(jié)。
2. 平均時間復雜度
最好情況時間復雜度和最壞情況時間復雜度對應的都是比較極端的情況奢赂，發(fā)生的概率比較小陪白。為了更好地表示平均情況下的時間復雜度，我們引入"平均時間復雜度"這個概念呈驶。
借助剛才查找變量x的例子：要查找的變量x在數(shù)組中的位置拷泽，有n+1種情況：在數(shù)組的0～n-1位置中和不在數(shù)組中。把每種情況下袖瞻，查找需要遍歷的元素個數(shù)累加起來，然后再除以n+1拆吆，就可以得到需要遍歷的元素個數(shù)的平均值聋迎，即：
大O時間復雜度表示法，可以忽略系數(shù)枣耀、低階霉晕、常量，所以這個公式可以簡化為O(n)捞奕。不過計算過程有點問題牺堰，就是我們剛才說的這個n+1種情況，出現(xiàn)的概率其實是不一樣的颅围。
要查找變量x伟葫，在數(shù)組和不在數(shù)組的概率都是1/2，在0～n-1這個n個位置的概率也是一樣的院促，為1/n筏养，而根據(jù)時間復雜度乘法法則（嵌套代碼復雜度是嵌套內外代碼復雜度的乘積）【如果對時間復雜度乘法法則不了解，建議點擊跳轉閱讀這篇文章：http://www.reibang.com/p/2d5e5f1bc77e 】常拓，要查找的數(shù)據(jù)出現(xiàn)在0～n-1中任意位置的概率就是1/n * 1/2 = 1/2n渐溶。所以如果把每種情況發(fā)生的概率考慮進去，那么平均時間復雜度的計算過程就變成了這樣：
這個值在概率論中叫做加權平均值弄抬，也叫做期望值茎辐，所以平均時間復雜度的全程應該叫加權平均時間復雜度或者期望時間復雜度。
用大O時間復雜度表示法表示掂恕，去掉系數(shù)和常量拖陆，上面示例代碼的加權時間復雜度依然是O(n)。
其實竹海，在大多數(shù)情況下慕蔚，并不需要區(qū)分最好、最壞斋配、平均情況時間復雜度三種情況孔飒，很多時候灌闺，只需要使用一個復雜度就可以滿足需求，就像以下兩篇文章中所講的那樣：
① http://www.reibang.com/p/2d5e5f1bc77e
② http://www.reibang.com/p/4c8fa84a9393
只有同一塊代碼在不同的情況下坏瞄，時間復雜度有量級的差距桂对，我們才會使用三種復雜度表示法來區(qū)分。
那何時平均時間復雜度加權鸠匀，何時不加權呢蕉斜？針對每個操作發(fā)生的概率都一樣的情況下，沒有必要使用加權平均時間復雜度缀棍，針對每個操作發(fā)生的概率不一樣的情況下宅此，有必要使用加權平均時間復雜度。
3. 后續(xù)
如果大家喜歡這篇文章爬范，歡迎點贊父腕！
如果想看更多 數(shù)據(jù)結構 方面的文章，歡迎關注!
