摘要訊息 : 使用替代法和歸納法解一個遞迴方程式.

0. 前言

在《分而治之演算法》中, 我們提到對採用了分而治之演算法的解決方案, 其時間複雜度可以寫成 \displaystyle {T(n)=\begin{cases} \Theta(1) & {n \leq c} \\ aT(\frac {n}{b}) + D(n) + C(n) & {n > c}. \end{cases}} 要分析分而治之演算法的時間複雜度, 必須要解這個遞迴方程式.

更新紀錄 :

• 2022 年 5 月 29 日進行第一次更新和修正.

1. 替代法

替代法將所有運算式中包含遞迴的部分都進行替換, 使用非遞迴的運算式表示. 最終, 通過整理和合併得到遞迴方程式的非遞迴表示.

例題 1. 使用替代法求解遞迴方程式 f(n) = \begin{cases} 2 & {n = 0} \\ f(n - 1) + 2 & {n \geq 1}. \end{cases}

解 :

當 n \geq 1 時, 有 \displaystyle {\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 \text { 個}} + f(2) \\ &= \underbrace{2 + 2 + ... + 2 + 2}_{n - 1 \text { 個}} + f(1) \\ &= \underbrace{2 + 2 + ... + 2 + 2 + 2}_{n \text { 個}} + f(0) \\ &= \underbrace{2 + 2 + ... + 2}_{n + 1 \text { 個}} \\ &= 2n + 2. \end {aligned}} 由於 n = 0 的時候, f(0) = 2 同樣滿足 f(n) = 2n + 2, 故當 n \geq 0 的時候, 有 \displaystyle {f(n) = 2n + 2}.

\blacksquare

例題 2. 使用替代法求解遞迴方程式 \displaystyle {f(n) = \begin{cases} c_{1} & {n = 1} \\ f \left ( \frac {n}{2} \right ) + c_{2} & {n > 1}. \end{cases}} 其中, c_{1} 和 c_{2} 為任意常數.

解 :

當 n > 1 時, 有 \displaystyle {\begin {aligned} f(n) &= f \left ( \frac {n}{2} \right ) + c_{2} \\ &= c_{2} + c_{2} + f \left ( \frac {n}{4} \right ) \\ &= ... \\ &= kc_{2} + f \left ( \frac {n}{2^{k}} \right ). \end{aligned}} 當 2^{k} = n 時, 有 \displaystyle {f(n) = kc_{2} + f(1) = kc_{2} + c_{1}}. 而考慮到 k = \log_{2}{n}, 故 \displaystyle {f(n) = c_{2} \log_{2}{n} + c_{1}.}

\blacksquare

例題 3. 使用替代法求解遞迴方程式 f(n) = \begin{cases} c & {n = 1} \\ af \left ( \frac {n}{b} \right ) + cn & {n > 1}. \end{cases}

解 :

僅考慮 n = b^{k} 時的情況. 當 n > 1 時, 有 \displaystyle {\begin {aligned} f(n) &= cn + af \left ( \frac {n}{a} \right ) \\ &= cn + a\left ( af \left ( \frac {n}{b^{2}} \right ) + c \frac {n}{b} \right ) \\ &= a^{2}f \left ( \frac {n}{b^{2}} \right ) + cn\left ( \frac {a}{b} + 1 \right ) \\ &= a^{2}\left ( c \frac {n}{b^{2}} + af \left ( \frac {n}{b^{3}} \right ) \right ) + cn \left ( \frac {a}{b} + 1 \right ) \\ &= a^{3}f \left ( \frac{n}{b^{3}} \right ) + cn\left ( \frac {a^{2}}{b^{2}} + \frac {a}{b} + 1 \right ) \\ &= a^{3}\left ( c \frac {n}{b^{3}} + af \left ( \frac {n}{b^{4}} \right ) + cn\left ( \frac {a^{2}}{b^{2}} + \frac {a}{b} + 1 \right ) \right ) \\ &= a^{4}f \left ( \frac {n}{b^{4}} \right ) + cn\left ( \frac {a^{3}}{b^{3}} + \frac {a^{2}}{b^{2}} + \frac {a}{b} + 1 \right ) \\ &= ... \\ &= a^{k}f \left ( \frac {n}{b^{k}} \right ) + cn\sum \limits_{i = 0}^{k - 1}\left ( \frac {a}{b} \right )^{i}. \end {aligned}} 當 b^{k} = n 時, 有 \displaystyle {f(n) = a^{k}f(1) + cn \sum \limits_{i = 0}^{k - 1}\left ( \frac {a}{b} \right )^{i} = a^{k}c + cn \sum \limits_{i = 1}^{k - 1}\left ( \frac {a}{b} \right )^{i}}. 而 \frac {n}{b^{k}} = 1, 故有 \displaystyle {\begin {aligned} f(n) &= a^{k}c + cn\sum \limits_{i = 1}^{k - 1}\left ( \frac {a}{b} \right )^{i} \\ &= a^{k}c \cdot 1 + cn\sum \limits_{i = 1}^{k - 1}\left ( \frac {a}{b} \right )^{i} \\ &= a^{k}c \cdot \frac {n}{b^{k}} + cn\sum \limits_{i = 1}^{k - 1}\left ( \frac {a}{b} \right )^{i} \\ &= (\frac {a}{b})^{k} \cdot cn + cn\sum \limits_{i = 0}^{k - 1}\left (\frac {a}{b} \right )^{i} \\ &= cn \sum \limits_{i = 0}^{k}\left ( \frac {a}{b} \right )^{i}. \end {aligned}}

顯然, \frac {a}{b} 很大程度上影響了 f(n), 接下來我們討論 a 和 b 的取值. 當 a = b 時, 有 \displaystyle {\sum \limits_{i = 0}^{k}\left ( \frac {a}{b} \right )^{i} = k + 1}; 當 a \neq b 時, 有 \displaystyle {\sum \limits_{i = 0}^{k}\left ( \frac {a}{b} \right )^{i} = \frac {\left ( \frac {a}{b} \right )^{k + 1} - 1}{\frac {a}{b} - 1} = \frac {1 - \left ( \frac {a}{b} \right )^{k + 1}}{1 - \frac {a}{b}}}. 當 a < b 時, 則 \frac {a}{b} < 1, 從而有 \displaystyle {\sum \limits_{i = 0}^{k}\left ( \frac {a}{b} \right )^{i} = \frac {1 - \left ( \frac {a}{b} \right )^{k + 1}}{1 - \frac {a}{b}} < \frac {1}{1 - \frac {a}{b}}}. 當 a > b 時, 則有 \displaystyle {\sum \limits_{i = 0}^{k}\left ( \frac {a}{b} \right )^{i} = \frac {\left ( \frac {a}{b} \right )^{k + 1} - 1}{\frac {a}{b} - 1}}.

由於 k = \log_{b}{n}. 根據《漸近分析基礎》中的定義 3, 即 Θ 記法的定義, 當 a = b 時, 我們可以得到 \displaystyle {\sum \limits_{i = 0}^{k}\left ( \frac {a}{b} \right )^{i} = k + 1 = \log_{b}{n} + 1 = \Theta(\log {n})}. 當 a < b 時, 由於 \lim \limits_{n \to \infty}\frac {1}{1 - \frac {a}{b}} = \lim \limits_{n \to \infty}\frac {1}{1 - \frac {a}{\sqrt[k]{n}}} = 1, 因此有 \displaystyle {\sum \limits_{i = 0}^{k}\left ( \frac {a}{b} \right )^{i} \leq \frac {1}{1 - \frac {a}{b}} = \Theta(1).} 當 a > b 時, 經過縮放我們可以得到 \displaystyle {\frac {\left ( \frac {a}{b} \right )^{k + 1} - 1}{\frac {a}{b} - 1} \geq \frac {\left ( \frac {a}{b} \right )^{k + 1} - 1}{\frac {a}{b}} \geq \frac {\left ( \frac {a}{b} \right )^{k + 1}}{\frac {a}{b}} = \left ( \frac {a}{b} \right )^{k}}. 根據《漸近分析基礎》中的定義 4, 即小 o 記法的定義, 有 \displaystyle {\begin {aligned} \frac {\left ( \frac {a}{b} \right )^{k + 1} - 1}{\frac {a}{b} - 1} \leq \frac {\left ( \frac {a}{b} \right )^{k + 1}}{\frac {a}{b} - 1} &= \frac {(t + 1)^{k + 1}}{t} \\ &= \frac {t^{k + 1} + o(t^{k + 1})}{t} \\ &= t^{k} + o(t^{k}) \\ &= \left ( \frac {a}{b} \right )^{k} + o \left ( \left ( \frac {a}{b} \right )^{k} \right ). \end {aligned}} 其中, t = \frac {a}{b} - 1. 結合《漸近分析基礎》中的定理 6, 即 Θ 記法比率定理, 於是有 \displaystyle {\sum \limits_{i = 0}^{k}\left ( \frac {a}{b} \right )^{i} = \Theta \left ( \left ( \frac {a}{b} \right )^{k} \right ) = \Theta \left ( \frac {a^{\log_{b}{n}}}{b^{\log_{b}{n}}} \right )}. 對於 a^{\log_{b}{n}}, 對其取自然對數可得 \displaystyle {\ln {a^{\log_{b}{n}}} = \log_{b}{n}\ln {a} = \frac {\ln {n}}{\ln {b}}\ln {a} = \frac {\ln {a}}{\ln {b}}\ln {n} = \log_{b}{a} \cdot \ln {n} = \ln {n^{\log_{b}{a}}},} 故 a^{\log_{b}{n}} = n^{\log_{b}{a}}. 那麼 \displaystyle {\sum \limits_{i = 0}^{k}\left ( \frac {a}{b} \right )^{i} = \Theta \left ( \frac {a^{\log_{b}{n}}}{b^{\log_{b}{n}}} \right ) = \Theta \left ( \frac {n^{\log_{b}{a}}}{n} \right ) = \Theta(n^{\log_{b}{a} - 1})}.

綜上所述, f(n) = cn \sum \limits_{i = 0}^{k}\left ( \frac {a}{b} \right )^{i} = \begin {cases} \Theta(n) & {a < b} \\ \Theta(n \log {n}) & {a = b} \\ \Theta(n^{\log_{b}{a}}) & {a > b}. \end {cases}

\blacksquare

現在, 我們重新審視分而治之演算法的時間複雜度 T(n), 它可以更加詳細地表示為 \displaystyle {T(n) = \begin {cases} \Theta(1) & {n \leq c} \\ \Theta(n) + D(n) + C(n) & {n > c \text { 且 } a < b} \\ \Theta(n\log {n}) + D(n) + C(n) & {n > c \text { 且 } a = b} \\ \Theta(n^{\log_{b}{a}}) + D(n) + C(n) & {n > c \text { 且 } a > b}. \end {cases}} 實際上我們可以看到, 例題 3 只是 T(n) 的一種特殊形式.

2. 查表法

如果我們記 g(n) = D(n) + C(n), 那麼 T(n) 實際上還可以進一步進行演算. 當 n \geq c 時, 有 \displaystyle {\begin {aligned} T(n) &= aT \left ( \frac {n}{b} \right ) + g(n) \\ &= a \left ( aT \left ( \frac {n}{b^{2}} \right ) + g \left ( \frac {n}{b} \right ) \right ) + g(n) \\ &= a^{2}T \left ( \frac {n}{b^{2}} \right ) + ag \left ( \frac {n}{b} \right ) + g(n) \\ &= ... \\&= a^{k}T(1) + \sum \limits_{i = 0}^{k - 1}a^{i}g \left ( \frac {n}{b^{i}} \right )(\text {其中, } k = \log_{b}{n}) \\ &= a^{k}T(1) + \sum \limits_{j = 1}^{k}a^{k - j}g \left ( \frac {n}{b^{k - j}} \right ) (\text {令 } j = k - i) \\ &= a^{k}T(1) + \sum \limits_{j = 1}^{k}a^{k - j}g \left ( \frac {n}{\frac {b^{k}}{b^{j}}} \right ) \\ &= a^{k}T(1) + \sum \limits_{j = 1}^{k}a^{k - j}g \left ( \frac {nb^{j}}{b^{\log_{b}{n}}} \right ) \\ &= a^{k}T(1) + \sum \limits_{j = 1}^{k}a^{k - j}g(b^{j}) \\ &= a^{k}T(1) + a^{k}\sum \limits_{j = 1}^{k}a^{-j}g(b^{j}) \\ &= a^{k}\left ( T(1) + \sum \limits_{j = 1}^{j}a^{-j}g(b^{j}) \right ). \end {aligned}} 在例題 3 中, 我們已經得到 a^{k} = a^{\log_{b}{n}} = n^{\log_{b}{a}}, 故有 \displaystyle {T(n) = n^{\log_{b}{a}}\left ( T(1) + \sum \limits_{j = 1}^{k}\frac {g(b^{j})}{a^{j}}\right )}. 又因 a^{j} = \left ( b^{\log_{b}{a}} \right )^{j} = \left ( b^{j} \right )^{\log_{b}{a}}, 因此有 \displaystyle {T(n) = n^{\log_{b}{a}}\left ( T(1) + \sum \limits_{j = 1}^{k}\frac {g(b^{j})}{\left ( b^{j} \right )^{\log_{b}{a}}} \right )}. 記 h(n) = \frac {g(n)}{n^{\log_{b}{a}}}, 則 \displaystyle {T(n) = n^{\log_{b}{a}}\left ( T(1) + \sum \limits_{j = 1}^{k}h(b^{j}) \right )}. 再記 f(n) = \sum \limits_{j = 1}^{k}h(b^{j}), 最終有 \displaystyle {T(n) = n^{\log_{b}{a}}\big (T(1) + f(n) \big )}.

現在, 對於不同的 h(n), 我們可以使用查表法使用對應的 f(n) 進行替換 :

例題 4. 使用查表法計算 T(n) = \begin {cases} c_{1} & {n = 1} \\ T \left ( \frac {n}{2} \right ) + 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(1), 通過查表可知 f(n) = \Theta(\log {n}). 最終有 \displaystyle {T(n) = \Theta(\log{n})}.

\blacksquare

例題 5. 使用查表法計算 \displaystyle {T(n) = \begin {cases} d & {n \leq 1} \\ 7T \left ( \frac {n}{2} \right ) + 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}}. 由於 2 - \log_{2}{7} < 0, 故 h(n) = O(1). 通過查表可知, 對應的 f(n) 為 f(n) = O(1). 於是, \displaystyle {T(n) = n^{\log_{2}{7}}(T(1) + O(1)) = \Theta(n^{\log_{2}{7}})}.

\blacksquare

3. 歸納法

使用歸納法求解遞迴方程式更多時候並不是在求解, 而是在驗證. 歸納法證明一個遞迴方程式的非遞迴表示成立, 基本步驟為 :

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

例題 6. 證明遞迴方程式 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.

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

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

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

\blacksquare