latex

Divide-and-Conquer Method Share

---

1. 阐释

代换法的关键在于利用数学归纳法。首先，要猜测一个大致的上界，并结合数学归纳法进行证明。然后，验证基本条件，确保递归满足这个上界。若无法准确猜测界限，可能需要一个一个试着证明，直到达到比较准确的界限为止。

2. 例子

3. 解释

这个递归表达式明显属于归并排序，时间复杂度为 。可以尝试用 进行证明。首先，假设小于 n 的情况符合这个式子，然后证明当 n 时也符合。

一般 n 和常数 c 都要很大，通常都趋近于无穷大。这个分析表明 n 必须大于 1，因为有对数运算。因此，我们需要验证 n=2 或 n=3 之类的基本情况。具体分析过程可以参考《算法导论》。

4. 注意

在代换法中，连续使用渐进符号 会导致忽略常数的影响。在数学递归论证中，应避免使用渐进符号，因为它们可能会导致论证不严谨。此外，代换法中必须有余项，尤其是负的余项。这是因为渐进符号可能会忽略常数的影响。

示例：若 n 为 ，首先 1=。假设小于 n 的情况都符合这个式子，则 n-1=。因此，n = (n-1) + 1 = 。这种情况是不行的，因为它忽略了常数的影响。

---

递归树方法是分析其他递归问题的有力工具。您可以参考此递归树的图片了解更多。

---

• 根据 PDF 所讲内容：
  • Case 1: 如果存在常数 ，使得 ，则 。
  • Case 2: 如果存在常数 k ，使得 ，则 。
  • Case 3: 如果存在常数 ，使得 ，并且 f(n) 满足正则性条件 对于某个常数 且足够大的 n，则 。

主要思路：比较 f(n) 和 即驱动函数和分水岭函数，即 表达式，就是要比较 f(n) 和 。

为什么会有这个 ?

因为前面的 由递归树分析得到，因此直接比较最高项。

1. case1: 对应数学符号是 >，即分水岭函数 > 驱动函数 f(n)。

• ，存在常数 。
• 那么 。

2. case2: 对应数学符号是 =，即分水岭函数 = 驱动函数 f(n)。

• ，k 是非负数，即 k 0。
• 。

3. case3: 对应数学符号是 <，即分水岭函数 < 驱动函数 f(n)。

• ，存在常数 。
• 若 ，其中 ，可判断 f(n) 是递减的，并且下一层是上一层的常数倍。因此，顶层是最大的，可以简化得出 。
• 。

---

Lemma Definition

令 a > 0 和 b > 1 为常数，且 f(n/b) 为在实数范围内定义的函数 。那么递归：

[ T(n) =

]

其解为 。

1. case 1 prove

f(n)=O()

2. case 2 prove

f(n)=

将上式代入公式()并反复应用习题3-5(c)，得