上一篇歸并排序基于分治思想通過遞歸的調(diào)用自身完成了排序，本篇是關(guān)于歸并排序的最后一部分——分析其時間復(fù)雜度。
這個過程中會解釋清楚在各種時間復(fù)雜度中經(jīng)?？吹降囊粋€記號——“l(fā)gn”（以2為底的對數(shù)函數(shù)）是如何產(chǎn)生的。
遞歸式
對歸并排序代碼進行逐行分析，當有n > 1個元素時，分解運行時間如下：
分解：第1行是判斷，第2行是分解步驟（僅僅計算中間位置），都只需要常量時間，因此D1(n) = Θ(1)，D2(n) = Θ(1)。
解決：原問題分解成了2個子問題，每個子問題的規(guī)模是原問題的1/2。為了求解一個規(guī)模為n/2的子問題，第3行和第4行，各需要T(n/2)的時間，所以一共需要2T(n/2)的時間來求解2個子問題。
合并：在合并算法中已經(jīng)知道在一個具有n個元素的數(shù)組上進行兩個子數(shù)組MERGE需要Θ(n)的時間，即第5行C(n) = Θ(n)。
將每行的執(zhí)行時間相加：
T(n) = 2T(n/2) + D1(n) + D2(n) + C(n) (當n > 1)
T(n)的表達式中又包含了T，所以上式稱為T(n)的遞歸式。
根據(jù)分析進行簡化可得到：
T(n) = 2T(n/2) + Θ(n) (當n > 1)
求解遞歸式
求解遞歸式，即得到描述T(n)與輸入規(guī)模n關(guān)系的函數(shù)表達式的過程。為方便起見，假設(shè)n剛好是2的冪（子數(shù)組總可以被2整除直到只有1個元素為止）。該假設(shè)不影響遞歸式解的增長量級。
重寫遞歸式為：T(n) = 2T(n/2) + cn (當n > 1)，然后手繪出“遞歸”層層展開的樣子——遞歸樹：
- 圖(a)為T(n)，是未進行遞歸時的表達；
- 圖(b)為擴展成一棵描繪遞歸式的等價樹，cn是樹根（代表遞歸的頂層算法中的代價），根的兩棵子樹是兩個較小的遞歸式T(n/2);
- 圖(c)是繼續(xù)擴展T(n/2)后的樣子。
如此層層遞歸擴展，得到一顆完整的遞歸樹如下：
將遞歸式完全擴展后，形成了完整的遞歸樹，一共是lgn+1層（如果n是8，則樹有l(wèi)g8+1=4層），每層的代價是cn，那么總代價cnlgn+cn，忽略低階項和常量c，即有T(n) = Θ(nlgn)。
關(guān)于Θ(nlgn)
現(xiàn)在知道時間復(fù)雜度中的lgn是如何產(chǎn)生的了：是基于遞歸的原因。
lgn即log2n，是以2為底的對數(shù)函數(shù)，比任何線性函數(shù)增長要慢，所以在足夠大的輸入情況下，在最壞情況下，運行時間為Θ(nlgn)的歸并排序?qū)?yōu)于運行時間為 Θ(n2)的插入排序。
共享協(xié)議：署名-非商業(yè)性使用-禁止演繹（CC BY-NC-ND 3.0 CN）
轉(zhuǎn)載請注明：作者黑猿大叔（簡書）
