對於合併排序法, 我們得到的時間複雜度遞迴方程式

T(n) = \begin{cases} 0 & {n = 0} \\ \Theta(1) & {n = 1} \\ T(\left \lfloor \frac {n}{2} \right \rfloor) + T(n - \left \lfloor \frac {n}{2} \right \rfloor) + \Theta(n) & {n > 1} \end{cases}

首先, 我們來討論為何 T(n) = \Theta(n \log {n}) 成立. 由於 T(n) 中含有取整函數, 並不容易計算, 因此我們不妨限定 \log_{2}{n} 為整數, 於是有

T(n) = \begin{cases} 0 & {n = 0} \\ \Theta(1) & {n = 1} \\ 2T(\frac {n}{2}) + \Theta(n) & {n > 1} \end{cases}

n \leq 1 時, 其操作的時間複雜度為常數級別, 不妨取某一個足夠大的常數 c_{1}, 使得當 n \leq 1 時, T(n) = c_{1}. 當 n > 1 時, 將序列進行劃分所需要的時間也是常數級別, 不妨取某一個足夠大的常數 c_{2} 使得 D(n) = c_{2}; 合併所需要的時間與 n 有關, 不妨取某一個足夠大的常數 c_{3} 使得 C(n) \leq c_{3}n. 於是有

T(n) \leq f(n) = \begin{cases} c_{1} & {n \leq 1} \\ 2T(\frac {n}{2}) + c_{2} + c_{3}n & {n > 1} \end{cases}

不難得到, f(n)T(n) 的一個上界. 故有 T(n) = O(f(n))

與之相反, 如果取足夠小的常數 c_{4}, c_{5}, c_{6}, 使得

T(n) \geq g(n) = \begin{cases} c_{4} & {n \leq 1} \\ 2T(\frac {n}{2}) + c_{5} + c_{6}n & {n > 1} \end{cases}

g(n)T(n) 的一個下界. 故有 T(n) = \Omega(g(n))

綜上所述, T(n) = \Theta(f(n)) = \Theta(g(n)). 而求解遞迴方程式 f(n)g(n) 可知

f(n) = g(n) = \Theta(n \log {n})

因此, T(n) = \Theta(n \log {n}). 不難看出, f(n) 是最壞情況下的時間複雜度, 而 g(n) 則是最好情況下的時間複雜度

上述分析中, 唯一沒有被解決的問題是如何得到 f(n) = g(n) = \Theta(n \log {n}). 這涉及到對遞迴方程式的求解, 因此求解遞迴方程式成了眼下的必要. 要求解一個遞迴方程式, 有以下幾種方法 :

  • 替代法
  • 歸納法
  • 特徵根法
  • 母函數法
  • 查表法

其中, 查表法對應表中的結論都是由前四個方法得到的

求解遞迴方程式的第一種方法是替代法, 即將所有運算式中包含遞迴的部分都進行替換, 使用非遞迴的運算式表示. 最終, 通過計算得到遞迴方程式的結果. 考慮 :

f(n) = \begin{cases} 2 & {n = 0} \\ f(n - 1) + 2 & {n \geq 1} \end{cases}

:

n \geq 1 時, 有

\begin {aligned} f(n) &= f(n - 1) + 2 \\ &= f(n - 2) + 2 + 2 \\ &= f(n - 3) + 2 + 2 + 2 \\ &= ... \\ &= \underbrace{2 + 2 + ... + 2}_{n - 2 個} + f(2) \\ &= \underbrace{2 + 2 + ... + 2 + 2}_{n - 1 個} + f(1) \\ &= \underbrace{2 + 2 + ... + 2 + 2 + 2}_{n 個} + f(0) \\ &= \underbrace{2 + 2 + ... + 2}_{n + 1 個} \\ &= 2n + 2 \\ &= \Theta(n) \end {aligned}

\blacksquare

再考慮 :

f(n) = \begin{cases} c_{1} & {n = 1} \\ f(\frac {n}{2}) + c_{2} & {n > 1} \end{cases}

其中, c_{1}c_{2} 為任意常數

:

n > 1 時, 有

\begin {aligned} f(n) &= f(\frac {n}{2}) + c_{2} \\ &= c_{2} + c_{2} + f(\frac {n}{4}) \\ &= ... \\ &= kc_{2} + f(\frac {n}{2^{k}}) \end{aligned}

2^{k} = n 時, f(n) = kc_{2} + f(1) = kc_{2} + c_{1}. 而 k = \log_{2}{n}, 故

f(n) = c_{2} \log_{2}{n} c_{1} = \Theta(\log {n})

\blacksquare

對於替換法, 考慮最後一個實例 :

f(n) = \begin{cases} c & {n = 1} \\ af(\frac {n}{b}) + cn & {n > 1} \end{cases}

:

僅考慮 n = b^{k} 時的情況, 當 n > 1 時, 有

\begin {aligned} f(n) &= cn + af(\frac {n}{a}) \\ &= cn + a(af(\frac {n}{b^{2}}) + c \frac {n}{b}) \\ &= a^{2}f(\frac {n}{b^{2}}) + cn(\frac {a}{b} + 1) \\ &= a^{2}(c \frac {n}{b^{2}} + af(\frac {n}{b^{3}})) + cn(\frac {a}{b} + 1) \\ &= a^{3}f(\frac{n}{b^{3}}) + cn(\frac {a^{2}}{b^{2}} + \frac {a}{b} + 1) \\ &= a^{3}(c \frac {n}{b^{3}} + af(\frac {n}{b^{4}}) + cn(\frac {a^{2}}{b^{2}} + \frac {a}{b} + 1)) \\ &= a^{4}f(\frac {n}{b^{4}}) + cn(\frac {a^{3}}{b^{3}} + \frac {a^{2}}{b^{2}} + \frac {a}{b} + 1) \\ &= ... \\ &= a^{k}f(\frac {n}{b^{k}}) + cn \sum \limits_{i = 0}^{k - 1}(\frac {a}{b})^{i} \end {aligned}

b^{k} = n 時, f(n) = a^{k}f(1) + cn \sum \limits_{i = 0}^{k - 1}(\frac {a}{b})^{i} = a^{k}c + cn \sum \limits_{i = 1}^{k - 1}(\frac {a}{b})^{i}. 而 \frac {n}{b^{k}} = 1, 故有

\begin {aligned} f(n) &= a^{k}c + cn \sum \limits_{i = 1}^{k - 1}(\frac {a}{b})^{i} \\ &= a^{k}c \cdot 1 + cn \sum \limits_{i = 1}^{k - 1}(\frac {a}{b})^{i} \\ &= a^{k}c \cdot \frac {n}{b^{k}} + cn \sum \limits_{i = 1}^{k - 1}(\frac {a}{b})^{i} \\ &= (\frac {a}{b})^{k} \cdot cn + cn \sum \limits_{i = 0}^{k - 1}(\frac {a}{b})^{i} \\ &= cn \sum \limits_{i = 0}^{k}(\frac {a}{b})^{i} \end {aligned}

a = b 時, \sum \limits_{i = 0}^{k}(\frac {a}{b})^{i} = k + 1; 當 a \neq b 時, \sum \limits_{i = 0}^{k}(\frac {a}{b})^{i} = \frac {(\frac {a}{b})^{k + 1} - 1}{\frac {a}{b} - 1} = \frac {1 - (\frac {a}{b})^{k + 1}}{1 - \frac {a}{b}}

a < b 時, 則 \frac {a}{b} < 1\sum \limits_{i = 0}^{k}(\frac {a}{b})^{i} = \frac {1 - (\frac {a}{b})^{k + 1}}{1 - \frac {a}{b}} < \frac {1}{1 - \frac {a}{b}} = \Theta(1)

a > b 時, 則 \sum \limits_{i = 0}^{k}(\frac {a}{b})^{i} = \frac {(\frac {a}{b})^{k + 1} - 1}{\frac {a}{b} - 1} = \Theta((\frac {a}{b})^{k}) = \Theta(\frac {a^{k}}{b^{\log_{b}{n}}}) = \Theta(\frac {a^{\log_{b}{n}}}{n}) = \Theta(\frac {n^{\log_{b}{a}}}{n})

由於 k = \log_{b}{n}, 故當 a = b 時, \sum \limits_{i = 0}^{k}(\frac {a}{b})^{i} = k + 1 = \log_{b}{n} + 1 = \Theta(\log {n})

綜上所述,

f(n) = \begin {cases}\Theta(n) & {a < b} \\ \Theta(n \log {n}) & {a = b} \\ \Theta(n^{\log_{b}{a}}) & {a > b} \end {cases}

\blacksquare

我們重新審視使用了分而治之思想的程式的運作時間 T(n). 對於任意常數 c, 有

T(n) = \begin {cases} \Theta(1) & {n \leq c} \\ aT(\frac {n}{b}) + D(n) + C(n) & {n > c} \end {cases}

結合最後一個實例, 我們可以得到

T(n) = \begin {cases} \Theta(1) &{n \leq c} \\\Theta(n) & {n > c\ 且\ a < b} \\\Theta(n \log {n}) & {n > c\ 且\ a = b} \\\Theta(n^{\log_{b}{a}}) & {n > c\ 且\ a > b} \end {cases}

在快速排序法 (我們還沒有講) 和合併排序法下, 都有 a = b 的特點, 因此它們的平均複雜度都為 \Theta(n \log {n})

實際上, 實例

f(n) = \begin{cases} c & {n = 1} \\ af(\frac {n}{b}) + cn & {n > 1} \end{cases}

是一般的分而治之遞迴方程式

T(n) = \begin {cases} \Theta(1) & {n \leq c} \\ aT(\frac {n}{b}) + D(n) + C(n) & {n > c} \end {cases}

的一個特殊形式. 我們不妨假設 T(1) = c_{0}, g(n) = D(n) + C(n) = c_{0}n. 使用替換法解這個遞迴方程式, 我們可以得到

\begin {aligned} T(n) &= aT(\frac {n}{b}) + g(n) \\ &= a(aT(\frac {n}{b^{2}}) + g(\frac {n}{b}) + g(n)) \\ &= a^{2}T(\frac {n}{b^{2}}) + ag(\frac {n}{b}) + g(n) \\ &= ... \\ &= a^{k}T(1) + \sum \limits_{i = 0}^{k - 1}a^{i}g(\frac {n}{b^{i}})\end {aligned}

其中, k = \log_{b}{n}. T(n) 可以繼續被簡化 :

\begin {aligned} T(n) &= a^{k}T(1) + \sum \limits_{i = 0}^{k - 1}a^{i}g(\frac {n}{b^{i}}) \\ &= a^{k}T(1) + \sum \limits_{j = 1}^{k}a^{k - j}g(b^{j})\ (令\ j = k - i) \\ &= a^{k}T(1) + a^{k}\sum \limits_{j = 1}^{k}a^{-j}g(b^{j}) \\ &= a^{k}(T(1) + \sum \limits_{j = 1}^{k}a^{-j}g(b^{j})) \end {aligned}

由於 a^{k} = a^{\log_{b}{n}}, 對這個等式兩側取自然對數, 有

k \ln {a} = \log_{b}{n} \ln {a} = \frac {\ln {n}}{\ln {b}} \cdot \ln {a} = \frac {\ln {a}}{\ln {b}} \cdot \ln {n} = \log_{b}{a} \cdot \ln {n}

於是, a^{k} = a^{\log_{b}{n}} = n^{\log_{b}{a}}, 故有

\begin {aligned} T(n) &= n^{\log_{b}{a}}(T(1) + \sum \limits_{j = 1}^{k}a^{-j}g(b^{j})) \\ &= n^{\log_{b}{a}}(T(1) + \sum \limits_{j = 1}^{k}\frac {g(b^{j})}{a^{j}}) \end {aligned}

又因為 a^{j} = (b^{\log_{b}{a}})^{j} = (b^{j})^{\log_{b}{a}}, 則

T(n) = n^{\log_{b}{a}}(T(1) + \sum \limits_{j = 1}^{k} \frac {g(b^{j})}{(b^{j})^{\log_{b}{a}}})

h(n) = \frac {g(n)}{n^{\log_{b}{a}}}, 則有

T(n) = n^{\log_{b}{a}}(T(1) + \sum \limits_{j = 1}^{k}h(b^{j}))

再記 f(n) = \sum \limits_{j = 1}^{k}h(b^{j}), 最終有

T(n) = n^{\log_{b}{a}}(T(1) + f(n))

有了上述推理, 對於不同的 h(n), 我們可以使用查表法將 h(n) 使用對應的 f(n) 進行替換 :

h(n) f(n)
O(n^{r}), r < 0 O(1)
\Theta(\log^{i}{n}), i \geq 0 \Theta(\frac {\log^{i + 1}{n}}{i + 1})
\Omega(n^{r}), r > 0 \Theta(h(n))

對於查表法的應用, 我們考慮實例 :

T(n) = \begin {cases} c_{1} & {n = 1} \\ T(\frac {n}{2}) + c_{2} & {n > 1} \end {cases}

:

容易地, 我們得到 a = 1, b = 2, g(n) = c_{2}. 因此, \log_{b}{a} = 0. 另外,

h(n) = \frac {g(n)}{n^{\log_{b}{a}}} = c_{2} = c_{2} \cdot log^{0}{n} = \Theta(\log {n})

\blacksquare

再考慮實例 :

T(n) = \begin {cases} d & {n \leq 1} \\ 7T(\frac {n}{2}) + cn^{2} &{n > 1} \end {cases}, 其中\ \log_{2}{n}\ 為整數

:

通過觀察, 我們可以得到 a = 7, b = 2, g(n) = cn^{2}. 因此, \log_{b}{a} = \log_{2}{7}. 另外,

h(n) = \frac {g(n)}{n^{\log_{b}{a}}} = \frac {cn^{2}}{n^{\log_{2}{7}}} = cn^{2 - \log_{2}{7}}</p> <p>由於 [latex]2 - \log_{2}{7} < 0, 故 h(n) = O(1). 於是, T(n) = n^{\log_{2}{7}}(T(1) + O(1)) = \Theta(n^{\log_{2}{7}})

\blacksquare

 

使用歸納法求解遞迴方程式更多時候並不是在求解, 而是在驗證. 考慮實例 :

f(n) = \begin {cases} 2 & {n = 0} \\ f(n - 1) + 3 & {n > 0} \end {cases}

我們使用歸納法來證明 f(n) = 3n + 2 = \Theta(n)

:

n = 1 時, f(1) = 3 + f(0) = 5. 因此, 當 [latex]n = 1 時結論成立

不妨假設當 n \leq k 時, f(n) = 3n + 2

n = k + 1 時, f(k + 1) = 3 + f(k) = 3 + 3k + 2 = 3k + 5. 因此, 當 n = k + 1 時, 結論仍然成立

綜上所述, f(n) = 3n + 2 = \Theta(n)

\blacksquare

歸納法時一種間接的數學證明方法, 我們曾經在文章《【初等數學】數學初步 (上篇)》中要求大家掌握歸納法, 其基本步驟為 :

  1. 歸納基礎 : 這是歸納法的起始步驟. 對於一個或者多個基礎值進行結論的驗證, 檢驗結論是否成立
  2. 歸納假設 : 假設 n \leq k 或者 n < k 時結論成立. 其中, k 為任意一個大於或者等於最大基礎值的整數
  3. 歸納推遞 : 根據歸納假設, 證明當 n = k + 1 或者 n = k 時, 結論成立
  4. 綜合上述三個步驟的結論, 得出結論成立