递归关系的全面解析与应用

### 递归关系的全面解析与应用 #### 1. 递归关系基础与主定理 递归关系在算法分析中起着至关重要的作用，它能帮助我们分析算法的时间复杂度。主定理是解决递归关系的重要工具，只要满足 \(f (n) = \Theta(n^k)\)（其中 \(k \geq 0\)），主定理就一定适用。 例如，对于 \(T (n) = T (\frac{4n}{5}) + \log^2 n\)： - 这里 \(a = 1\)，\(b = \frac{5}{4}\)，\(f (n) = \log^2 n\)，\(n^{\log_b(a)} = 1\)。\(f (n)\) 不是多项式级别的大于 \(n^{\log_b(a)}\)，但规则 4 适用（\(k = 2\)），所以 \(T (n) = \Theta(\log^3(n))\)。 - 再如 \(T (n) = 2T (\frac{n}{4}) + \sqrt{n} \log \log(n)\)，\(a = 2\)，\(b = 4\)，\(f (n) = \sqrt{n} \log \log n\)，\(n^{\log_b(a)} = n^{\frac{1}{2}}\)，\(f (n)\) 不是多项式级别的大于 \(n^{\log_b(a)}\)，主定理不适用。 #### 2. 迭代法求解递归关系 迭代法是通过不断迭代递推公式，逐步找到通项公式的方法。以下是一些简单递归关系的例子及求解过程： |序号|递归关系|求解过程| | ---- | ---- | ---- | |1| \(T(1) = d\)，\(n > 1\) 时，\(T(n) = T(n–1) + c\) | \(T_n = T_{n−1} + c = (T_{n−2} + c) + c = T_{n−2} + 2c = \cdots = T_1 + (n - 1)c = d + (n - 1)c\) | |2| \(T(0) = 0\)，\(n > 1\) 时，\(T(n) = 2T(n–1) + 1\) | \(T (n) = 2 (T (n - 1)) + 1 = 2^2 (T (n - 2)) + (2 + 1) = \cdots = 2^n (T (0)) + (2^{n - 1} + \cdots + 2 + 1) = 2^n - 1\) | |4| \(T(1) = 1\)，\(n > 1\) 时，\(T(n) = 2T(n–2) + 1\) | \(T (n) = 2T (n - 2) + 1 = 2^2T (n - 3) + (2 + 1) = \cdots = 2^nT (n - 2) + (2^{n - 1} + \cdots + 2 + 1)\) | #### 3. 汉诺塔问题的递归分析 汉诺塔问题的算法如下： ```c void Hanoi(int n, A, B, C) { if (n == 1) move a disk from A to C else { Hanoi(n - 1, A, C, B) move a disk from A to C Hanoi(n - 1, B, A, C) } } ``` 设 \(T(n)\) 表示该函数对于 \(n\) 的调用次数，递归函数为： \[T (n) = \begin{cases} 0, & n = 0 \\ 2T (n - 1) + 1, & n > 1 \end{cases} \] 通过迭代法求解： \[ \begin{align*} T(n) &= 2T(n - 1) + 1\\ &= 2(2T(n - 2) + 1) + 1 = 2^2T(n - 2) + 2 + 1\\ &= \cdots\\ &= 2^nT(0) + 2^{n - 1} + \cdots + 2 + 1\\ &= 2^n - 1 \end{align*} \] 所以汉诺塔问题的时间复杂度为 \(O(2^n)\)。 #### 4. 常系数齐次线性递归方程 对于常系数齐次线性递归方程，我们可以通过特征函数来求解。例如： - 对于 \(T(n) = 2T(n - 1) - 3T(n - 2)\)，特征方程为 \(x^2 - 2x + 3 = 0\)，解得 \(x_1 = 1 + \sqrt{2}\)，\(x_2 = 1 - \sqrt{2}\)，则 \(T(n) = c_1(1 + \sqrt{2})^n + c_2(1 - \sqrt{2})^n\)，再根据初始条件 \(T(0) = 1\)，\(T(1) = 2\) 确定 \(c_1\) 和 \(c_2\) 的值。 - 斐波那契数列 \(F(n) = F(n - 1) + F(n - 2)\)，特征方程为 \(F^2 - F - 1 = 0\)，解得 \(r_1, r_2 = \frac{1 \pm \sqrt{5}}{2}\)，则 \(F(n) = C_1(\frac{1 + \sqrt{5}}{2})^n + C_2(\frac{1 - \sqrt{5}}{2})^n\)，根据 \(F(0) = 1\)，\(F(1) = 1\) 确定系数。 以下是部分常系数齐次线性递归方程的求解结果： |序号|递归方程|特征根|通解| | ---- | ---- | ---- | ---- | |18| \(T(n) = 2T(n - 1) - 3T(n -