Divide-and-Conquer Method Share#
\section{Substitution Method}
1. 阐释#
代换法的关键在于利用数学归纳法。首先，要猜测一个大致的上界，并结合数学归纳法进行证明。然后，验证基本条件，确保递归满足这个上界。若无法准确猜测界限，可能需要一个一个试着证明，直到达到比较准确的界限为止。
2. 例子#
$$ T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n) $$3. 解释#
这个递归表达式明显属于归并排序，时间复杂度为 $\mathcal{O}(n \log n)$。可以尝试用 $c n \log n$ 进行证明。首先，假设小于 n 的情况符合这个式子，然后证明当 n 时也符合。
$$ \begin{align} T(n) &= 2T\left(\frac{n}{2}\right) + \Theta(n) \\ &= 2 \cdot c \cdot \left(\frac{n}{2}\right) \cdot \log\left(\frac{n}{2}\right) + \Theta(n) && \text{代入猜想} \\ &= c n \cdot (\log n - \log 2) + \Theta(n) && \text{展开} \\ &= c n \cdot \log n - c n \cdot \log 2 + \Theta(n) \\ &\leq c n \cdot \log n && \text{得到不等式} \end{align} $$一般 n 和常数 c 都要很大，通常都趋近于无穷大。这个分析表明 n 必须大于 1，因为有对数运算。因此，我们需要验证 n=2 或 n=3 之类的基本情况。具体分析过程可以参考《算法导论》。
4. 注意#
在代换法中，连续使用渐进符号 $\mathcal{O}$ 会导致忽略常数的影响。在数学递归论证中，应避免使用渐进符号，因为它们可能会导致论证不严谨。此外，代换法中必须有余项，尤其是负的余项。这是因为渐进符号可能会忽略常数的影响。
示例：若 n 为 $\Theta(1)$，首先 1=$\Theta(1)$。假设小于 n 的情况都符合这个式子，则 n-1=$\Theta(1)$。因此，n = (n-1) + 1 = $\Theta(1)$。这种情况是不行的，因为它忽略了常数的影响。
\section{Recursion-Tree Method}
递归树方法是分析其他递归问题的有力工具。您可以参考此递归树的图片了解更多。
\section{Master Method}
- 根据 PDF 所讲内容：
- Case 1: 如果存在常数 $\epsilon > 0$，使得 $f(n)=O(n^{log_ba-\epsilon})$，则 $T(n)=\Theta(n^{log_ba})$。
- Case 2: 如果存在常数 k $\geq 0$，使得 $f(n)=\Theta(n^{log_ba} \cdot lg^k n)$，则 $T(n)=\Theta(n^{log_ba} \cdot lg^{k+1}n)$。
- Case 3: 如果存在常数 $\epsilon > 0$，使得 $f(n)=\Omega(n^{log_ba+\epsilon})$，并且 f(n) 满足正则性条件 $ af(n/b) \leq cf(n) $ 对于某个常数 $c < 1$ 且足够大的 n，则 $T(n) = \Theta(f(n))$。
主要思路：比较 f(n) 和 $n^{log_b(a)}$ 即驱动函数和分水岭函数，即 $T(n)=aT(n/b)+f(n)$ 表达式，就是要比较 f(n) 和 $n^{log_b(a)}$。#
为什么会有这个 $n^{log_b(a)}$?#
因为前面的 $T(n)$ 由递归树分析得到，因此直接比较最高项。
1. case1: 对应数学符号是 >，即分水岭函数 $n^{log_b(a)}$ > 驱动函数 f(n)。#
- $f(n)=O(n^{log_b(a)-\epsilon})$，存在常数 $\epsilon > 0$。
- 那么 $T(n)=\Theta(n^{log_b(a)})$。
2. case2: 对应数学符号是 =，即分水岭函数 $n^{log_b(a)}$ = 驱动函数 f(n)。#
- $f(n)=\Theta(n^{log_b(a)}*lg^k(n))$，k 是非负数，即 k $\geq$ 0。
- $T(n)=\Theta(n^{log_b(a)}*lg^{k+1}(n))$。
3. case3: 对应数学符号是 <，即分水岭函数 $n^{log_b(a)}$ < 驱动函数 f(n)。#
- $f(n)=\Omega(n^{log_b(a)+\epsilon})$，存在常数 $\epsilon > 0$。
- 若 $af(n/b)\leq(1-\epsilon')*f(n)$，其中 $\epsilon' > 0$，可判断 f(n) 是递减的，并且下一层是上一层的常数倍。因此，顶层是最大的，可以简化得出 $\Theta(f(n))$。
- $T(n)=\Theta(f(n))$。
\section{Master Method Prove}
Lemma Definition#
令 a > 0 和 b > 1 为常数，且 f(n/b) 为在实数范围内定义的函数 $n\geq 1$。那么递归：
\[ T(n) = \begin{cases} \Theta(1), & \text{if } 0\leq n<1 \\ aT(n/b)+f(n), & \text{if } n \geq 1 \end{cases} \]其解为 $T(n) =\Theta(n^{\log_b a}) + \sum\limits_{j=0}^{\lfloor{log_bn}\rfloor}a^j f(n/b^j)$。
1. case 1 prove#
f(n)=O($n^{log_b(a)}$)
$$ \begin{align} g(n) &= \sum_{j=0}^{\lfloor{log_b{n}}\rfloor}a^j*f\left(\frac{n}{b^j}\right) \\ &= \sum_{j=0}^{\lfloor{log_b{n}}\rfloor}a^j*O\left(\left(\frac{n}{b^j}\right)^{log_b(a)-\epsilon}\right) \\ &= O\left(n^{log_b(a)-\epsilon}\sum_{j=0}^{\lfloor{log_b{n}}\rfloor}\frac{a^j}{(b^j)^{log_b(a)-\epsilon}}\right) \\ &= O\left(n^{log_b(a)-\epsilon}\sum_{j=0}^{\lfloor{log_b{n}}\rfloor}(b^\epsilon)^j\right) \\ & \leq O\left(n^{log_b(a)-\epsilon}*\frac{n^\epsilon*b^\epsilon-1}{b^\epsilon-1}\right) \\ &= O\left(n^{log_b(a)}\right) \end{align} $$2. case 2 prove#
f(n)=$\Theta(n^{log_b(a)}*lg^k(n))$
$$ \begin{align} &= \Theta\left(n^{\log_b a} \cdot \lg^k n - {j \cdot \log_b b \cdot \lg^k n}\right) \tag{eq:1} \\ &= \Theta\left(n^{\log_b a} \cdot \lg^k n\right) \quad (\text{因为 } b > 1) \end{align} $$将上式代入公式(\ref{eq:1})并反复应用习题3-5(c)，得
$$ \begin{align} g(n)&= \Theta\left(\sum_{j=0}^{\lfloor \log_b n\rfloor} a^j \left(\frac{n}{b^j}\right)^{\log_b a} \cdot \lg^k \left(\frac{n}{b^j}\right)\right) \\ &= \Theta\left(n^{\log_b a} \cdot \sum_{j=0}^{\lfloor \log_b n\rfloor} \frac{a^j}{(b^j)^{\log_b a}} \cdot \lg^k \left(\frac{n}{b^j}\right)\right) \\ &= \Theta\left(n^{\log_b a} \cdot \sum_{j=0}^{\lfloor \log_b n\rfloor} \left(\frac{a}{b^{\log_b a}}\right)^j \cdot \lg^k \left(\frac{n}{b^j}\right)\right) \\ &= \Theta\left(n^{\log_b a} \cdot \sum_{j=0}^{\lfloor \log_b n\rfloor} \left(\frac{a}{b^{\log_b a}}\right)^j \cdot \lg^k n\right) \\ &= \Theta\left(n^{\log_b a} \cdot \sum_{j=0}^{\lfloor \log_b n\rfloor} \left(\frac{a}{b^{\log_b a}}\right)^j\right) \cdot \lg^k n \\ &= \Theta\left(n^{\log_b a} \cdot \frac{\left(\frac{a}{b^{\log_b a}}\right)^{\lfloor \log_b n\rfloor + 1} - 1}{\frac{a}{b^{\log_b a}} - 1}\right) \cdot \lg^k n \\ &= \Theta\left(n^{\log_b a} \cdot \frac{\left(\frac{a}{b^{\log_b a}}\right)^{\log_b n} \cdot \frac{a}{b^{\log_b a}} - 1}{\frac{a}{b^{\log_b a}} - 1}\right) \cdot \lg^k n \\ &= \Theta\left(n^{\log_b a} \cdot \frac{a^{\log_b n} - b^{\log_b a}}{a - b}\right) \cdot \lg^k n \\ &= \Theta\left(n^{\log_b a} \cdot \frac{a^{\log_b n}}{a - b}\right) \cdot \lg^k n \\ &= \Theta\left(n^{\log_b a} \cdot \frac{n^{\log_b a}}{a - b}\right) \cdot \lg^k n \\ &= \Theta\left(\frac{n^{\log_b a + 1}}{a - b}\right) \cdot \lg^k n \\ &= \Theta\left(\frac{n^{\log_b a} \cdot n}{a - b}\right) \cdot \lg^k n \\ &= \Theta\left(\frac{n^{\log_b a} \cdot n}{a - b} \cdot \lg^k n\right) \\ &= \Theta\left(\frac{n^{\log_b a} \cdot n \cdot \lg^k n}{a - b}\right) \end{align} $$