特征方程

1. 分治递推关系 (Divide and Conquer Recurrence)

这类关系用于分析将问题分解为小规模子问题的算法，如归并排序等。

问题实例

求解递推关系式：


最终答案: 该算法的时间复杂度为 Θ(N log²N)。

方法一：主方法 (Master Theorem)

主方法用于求解形如 T(N) = aT(N/b) + f(N) 的递推式。

• 识别参数:

• a = 2 (子问题数量)

• b = 2 (子问题规模缩小因子)

• f(N) = N log N (划分与合并的成本)

• 计算 N^(log_b a):

• 比较 f(N) 与 N^(log_b a):

• 比较 f(N) = N log N 和 N。

• f(N) 渐进大于 N，但并非多项式级别的大。

• 应用主方法扩展情况:

• 若 f(N) = Θ(N^(log_b a) * log^k N) 且 k ≥ 0，则 T(N) = Θ(N^(log_b a) * log^(k+1) N)。

• 在本例中，f(N) = N log N = N * (log N)¹，符合该形式，其中 k=1。

• 得出结论:

方法二：递归树法 (Recursion Tree Method)

通过将递推关系可视化为一棵树来求解。

• 各层代价分析:

• 第 0 层 (根): N log N

• 第 1 层: 2 * (N/2)log(N/2) = N log(N/2)

• 第 2 层: 4 * (N/4)log(N/4) = N log(N/4)

• 第 i 层: 2^i * (N/2^i)log(N/2^i) = N log(N/2^i) = N(log N - i) (假设 log 以 2 为底)

• 树的高度:

• 递归在 N/2^h = 1 时停止，解得树高 h = log N。

• 总代价求和:

• 令 k = log N，求和部分为 k + (k-1) + ... + 1 = k(k+1)/2。

• 得出结论:

• 取最高阶项，得到时间复杂度为 Θ(N log²N)。

---

2. 两种递推关系的核心区别

分治递推关系和线性常系数递推关系是完全不同的两类问题，不能混用求解方法。

特征	线性常系数递推关系	分治递推关系
典型形式	fₙ = c₁fₙ₋₁ + c₂fₙ₋₂	T(N) = aT(N/b) + f(N)
变量变化	步进式/减法 (n-1, n-2)	分割式/除法 (N/b)
适用场景	序列问题 (如斐波那契)	分治算法复杂度分析
求解工具	特征方程法	主方法、递归树法
解的形式	指数形式 (如 A⋅r₁ⁿ + B⋅r₂ⁿ)	多项式对数形式 (如 N log N)

---

3. 线性常系数递推关系与特征方程法

这类关系描述一个序列的项是其前面若干项的线性组合。

求解核心思想

• 猜测解的形式: 猜测解具有指数形式 fₙ = rⁿ。
• 为何猜测有效: 指数函数在移位操作下具有结构不变性（rⁿ⁻¹ 是 rⁿ 的常数倍），这与递推关系的结构完美匹配。通过代入该猜测，可以将递推关系转化为代数方程（特征方程）。

求解步骤示例

• 递推关系: fₙ = fₙ₋₁ + 2fₙ₋₂
• 代入猜测: rⁿ = rⁿ⁻¹ + 2rⁿ⁻²
• 化简得特征方程: 两边同除以 rⁿ⁻²，得 r² = r + 2，即 r² - r - 2 = 0。
• 求解特征根: (r-2)(r+1) = 0，解得 r₁ = 2, r₂ = -1。
• 写出通解: fₙ = A⋅(2)ⁿ + B⋅(-1)ⁿ。常数 A 和 B 由初始条件确定。

通项公式的构成

通项公式的项数严格等于特征方程的阶数。

情况一：无重根 (Distinct Roots)

如果一个 k 阶特征方程有 k 个不同的根 r₁, r₂, ..., rₖ，则通项公式有 k 项。

• 形式: fₙ = A₁r₁ⁿ + A₂r₂ⁿ + ... + Aₖrₖⁿ

情况二：有重根 (Repeated Roots)

如果特征根 r 是一个 k 重根，它将贡献 k 个线性无关的项。

• 处理方法: 在基础项 rⁿ 的基础上，乘以 n 的幂次 (n⁰, n¹, ..., nᵏ⁻¹)。
• 形式 (k重根r): fₙ = (A₁ + A₂n + A₃n² + ... + Aₖnᵏ⁻¹)rⁿ
• 示例:
• 递推关系: fₙ = 4fₙ₋₁ - 4fₙ₋₂
• 特征方程: r² - 4r + 4 = 0，即 (r-2)² = 0
• 特征根: r=2 (二重根)
• 通项公式: fₙ = (A + Bn)⋅2ⁿ = A⋅2ⁿ + B⋅n⋅2ⁿ。项数依然是2，等于方程阶数。