Solving Recurrence

算法
2.4k 词

Substitution method (考点)

Steps of the substitution method for solving recurrences:
i. Guess the form of the solution.
ii. Use the mathematical induction to find the constants and show that the solution works.
This method is powerful, but we must be able to guess the form of the answer in order to apply it.

明确上下界

Example

1. 递归式

我们从递归式出发：

直觉上，它应该是 O()。

2. 猜测解的形式

猜测 ，其中 c>0 是一个常数。
目标：证明这个不等式在合适的 c下对充分大的 n 成立。

3. 归纳假设与代入

假设对于所有比 n 小的正整数 m，不等式成立：

特别地对 使用假设：

4. 代回递归式

代入原式：

化简：

只要 ，就有

5. 基例问题

如果从 n=1 开始 induction，遇到麻烦：

  • T(1)=1，

  • 但 ，任何 c 都满足不了。

因此 n=1 不能作为基例。解决办法：
在 O-符号定义中，只需要存在某个常数 ，当 时不等式成立即可。
所以我们只需要验证从 n=2或 n=3开始。

6. 验证小规模基例

计算：

验证它们是否满足

选择 c=2：

  • 对 n=2，右边是 ，刚好满足；

  • 对 n=3，右边是 ，也满足。

7. 完成归纳

因为归纳基例成立，且在 时递归推导也成立，所以

因此：

总结：
证明的逻辑顺序是：

  1. 猜测解 → O(nlog⁡n)；

  2. 用归纳假设 → 代入递归 → 化简；

  3. 得出不等式条件 → 只要 成立；

  4. 发现 n=1 有问题，但 OO-符号只要求大规模时成立，所以换成从 n=2 开始；

  5. 选择合适的常数 c=2 验证小规模基例；

  6. 完成归纳，证明 T(n)=O(nlog⁡n).

Recursion-tree method

用于猜解是多少。

We create a recursion tree for the recurrence.

image.png

image.png

Master Theorem

core idea of the Master Theorem.

When you see a divide-and-conquer recurrence

you need to consider two parts:

  1. Recursive part (): how many subproblems (a) you create and how much smaller each is (n/b).

    • This determines the total work from recursion itself.

    • Think of it as the “tree branching factor.”

  2. Combine part (f(n)): the extra cost outside the recursion (splitting, merging, etc.).

    • This cost appears at every level of the recursion tree.

Then you compare the growth of these two to see which dominates. The rule is:

  • If (f(n)) grows slower than the recursive work, recursion dominates.

  • If (f(n)) grows faster, the combine dominates.

  • If they grow about the same, you get an extra (\log n) factor.

That’s why:

  • () ⇒ recursion (n) and combine (n) are same order → ().

  • () ⇒ recursion bigger → ().

  • () ⇒ combine bigger → ().

So yes — you always analyze both parts together.