algorithm - Big O n^(lg3) 中的 Karatsuba 算法通过替换证明

Question

Karatsuba算法涉及递归关系T(n) = 3T(n/2) + n。

通过递归树的方法，我们可以近似的大OT为O(nlog23)

但是，通过替换方法，我无法验证通过递归树方法找到的近似结果

我将简单地使用lg 3to 表示。log23

替代方法：

Hypothesis -> T(n) <= cnlg 3 where c is a positive constant
Proof -> T(n) <= 3c(n/2)lg 3 + n
                  =  cnlg 3 + n

但是证明的第 2 步表明，由于 n 项，我无法证明我的假设。

我修改了证明的第 2 步

T(n) <= cnlg 3 + nlg 3
      = (c+1)nlg 3

后来意识到我犯了一个错误，因为这个假设没有得到证实。

T(n) <= cnlg 3必须证明，不是T(n) <= (c+1)nlg 3

但答案T(n)是O(nlg 3)

Answer 1

使用代入法时，有时必须加强归纳假设并猜测一个更复杂的表达式形式，该表达式使递归上限。

尝试猜测 T(n) ≤ c ₀ n ^{lg 3} - c ₁ n 的形式。既然您要减去 c ₁ n 形式的某些项，您可能可以通过使用一些线性项来抵消稍后添加的 n 项来使递归计算出来。

例如：

T(n) ≤ 3T(n / 2) + n

≤ 3(c ₀ (n/2) ^{lg 3} - c ₁ (n/2)) + n

= 3(c ₀ (n/2) ^{lg 3} ) - 3c ₁ n/2 + n

现在，选择 c ₁使得 -3c ₁ n/2 + n = -c ₁ n。这解决了

-3c ₁ n/2 + n = -c ₁ n

-3c ₁ /2 + 1 = -c ₁

-3c ₁ + 2 = -2c ₁

2 = c ₁

然后，选择 c ₁将使您成功取消 +n 项，从而使归纳成功。

希望这可以帮助！