代碼千千萬，有些代碼邏輯會很複雜，是以為了更細化的分析算法的複雜度，再複雜度分析方面引入了4個知識點：
1.最好情況時間複雜度（best case time complexity）。
2.最壞情況時間複雜度（worst case time complexity）。
3.平均情況時間複雜度（average case time complexity）。
4.均攤時間複雜度（amortized time complexity）。
示例如下(限定條件:0<n且0<x且n和x為整數)：
這段代碼邏輯非常簡單，再此不描述。需要重點分析的是循環這一段代碼，這段代碼根據x值的不同，時間複雜度也有差別：
1.當x>n時，此代碼的時間複雜度是O(n)。
2.當1<=x<=n時，時間複雜度是一個我們不确定的值，取決于x的值。
3.當x=1時，時間複雜度是O(1)。
這段代碼在不同情況下，其時間複雜度是不一樣的。是以為了描述代碼在不同情況下的不同時間複雜度，我們引入了最好、最壞、平均時間複雜度。
最好情況時間複雜度，表示在最理想的情況下，執行這段代碼的時間複雜度。
上述示例就是當x=1的時候，循環的第一個判斷就跳出，這個時候對應的時間複雜度就是最好情況時間複雜度。
最壞情況時間複雜度，表示在最糟糕的情況下，執行這段代碼的時間複雜度。
上述示例就是n<x的時候，我們要把整個循環執行一遍，這個時候對應的時間複雜度就是最壞情況時間複雜度。
最好和最好情況是極端情況，發生的機率并不大。為了更有效的表示平均情況下的時間複雜度，引入另一個概念：平均情況時間複雜度。
分析上面的示例代碼，判斷x在循環中出現的位置，有n+1種情況：1<=x<=n 和n<x。
我們将所有情況下代碼執行的次數累加起來（（1+2+3....+n）+n），然後再除以所有情況數量（n+1），就可以得到需要周遊次數的平均值。
平均情況複雜度為：
$ \frac{((1+2+3...+n)+n)}{(n+1)}=\frac{n(n+3)}{2(n+1)} $
推導過程：
$ \because 1+2+3...+n=n+(n-1)+(n-2)...+1 $
$ \therefore (1+2+3...+n)=\frac{n(1+n)}{2} $
$ \therefore (1+2+3...+n)+n= \frac{n(3+n)}{2} $
大O表示法，會省略系數、低階、常量，是以平均情況時間複雜度是O(n)。
但是這個平均複雜度沒有考慮各自情況的發生機率，這裡的n+1個情況，它們的發生機率是不一樣的，是以還需要引入各自情況發生的機率再具體分析。
x要麼在1~n中，要麼不在1~n中，是以它們的機率都是$\frac{1}{2}$。
同時資料在1~n中各個位置的機率都是一樣的為$\frac{1}{n}$。根據機率乘法法則，x在1~n中任意位置的機率是$\frac{1}{2n}$。
是以在前面推導過程的基礎上，我們把每種情況發生的機率考慮進去，那麼平均情況時間複雜度的計算過程變成：
考慮機率的平均情況複雜度為：
$(1\frac{1}{2n}+2\frac{1}{2n}+3\frac{1}{2n}...+n\frac{1}{2n})+n\frac{1}{2}=\frac{3n+1}{4}$
$\because (1+2+3...+n)=\frac{n(1+n)}{2}$
$\therefore (1\frac{1}{2n}+2\frac{1}{2n}+3\frac{1}{2n}...+n\frac{1}{2n})=\frac{1}{2n}(1+2+3...+n)=\frac{1}{2n}*\frac{n(1+n)}{2} =\frac{1+n}{4}$
$\therefore (1\frac{1}{2n}+2\frac{1}{2n}+3\frac{1}{2n}...+n\frac{1}{2n})+n\frac{1}{2}=\frac{1+n}{4} +n\frac{1}{2}=\frac{3n+1}{4}$
這就是機率論中的權重平均值，也叫做期望值，是以平均時間複雜度全稱叫：權重平均時間複雜度或者期望時間複雜度。
引入機率之後，平均複雜度變為O($\frac{3n+1}{4}$)，忽略系數及常量後，最終得到權重平均時間複雜度為O(n)。
注意：
多數情況下，我們不需要區分最好、最壞、平均情況時間複雜度。隻有同一塊代碼在不同情況下時間複雜度有量級差距，我們才會區分3種情況，為的是更有效的描述代碼的時間複雜度。
均攤複雜度是一個更加進階的概念，它是一種特殊的情況，應用的場景也更加特殊和有限。
對應的分析方式稱為：攤還分析或平攤分析。
示例如下（限定條件：0<=x<=n且0<=n且n,x為整數）：
分析上述案例的時間複雜度：
最理想情況下x!=n，隻執行一次指派即可推出，是以最好時間複雜度為O(1)。
最壞的情況下x=n，要執行一次循環累加和的操作，是以最好時間複雜度為O(n)。
平均的情況下，因為限定條件0<=x<=n，x在0~n中存在的位置可以分為n+1種情況(0到n)。
當0<=x<n時，時間複雜度為O(1)。但是x=n的時候是一個例外，它的複雜度是O(n)。
而且這n+1種情況發生的機率都是一樣的，為$\frac{1}{n+1}$。是以根據權重平均的計算方法，
平均時間複雜度為：
$ (1\tfrac{1}{n+1}+1\tfrac{1}{n+1}+1\tfrac{1}{n+1}+...+1\tfrac{1}{n+1})+n\tfrac{1}{n+1} = \tfrac{2n}{n+1} $
$(1\tfrac{1}{n+1}+1\tfrac{1}{n+1}+1\tfrac{1}{n+1}+...+1\tfrac{1}{n+1})+n\tfrac{1}{n+1}$
$=n\tfrac{1}{n+1}+n\tfrac{1}{n+1}$
$=\tfrac{2n}{n+1}$
當省略系數及常量後，平均時間複雜度為O(1)。
攤還分析法
分析上述示例的平均複雜度分析并不需要如此複雜，無需引入機率論的知識。
因為通過分析可以看出，上述示例代碼複雜度大多數為O(1)，極端情況下複雜度才較高為O(n)。同時複雜度遵循一定的規律，一般為1個O(n)，和n個O(1)。針對這樣一種特殊場景使用更簡單的分析方法：攤還分析法。
通過攤還分析法得到的時間複雜度為均攤時間複雜度。
大緻思路：每一次O(n)都會跟着n次O(1)，是以把耗時多的複雜度均攤到耗時低的複雜度。得到的均攤時間複雜度為O(1)。
應用場景：均攤時間複雜度和攤還分析應用場景較為特殊，對一個資料進行連續操作，大部分情況下時間複雜度都很低，隻有個别情況下時間複雜度較高。而這組操作其存在前後連貫的時序關系。
這個時候我們将這一組操作放在一起分析，将高複雜度均攤到其餘低複雜度上，是以一般均攤時間複雜度就等于最好情況時間複雜度。
注意：均攤時間複雜度是一種特殊的平均複雜度（特殊應用場景下使用），掌握分析方式即可。
作者：Jonins
出處：http://www.cnblogs.com/jonins/
個人原創，若有錯誤或補充請聯系作者。
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。