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

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$