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

Question

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

通过递归树的方法，我们可以近似出T的大O成为O(n<sup>log<sub>2</sub>3</sup>)

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

我将简单地使用 lg 3意思是log<sub>2</sub>3 .

替换方法:

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

但是证明的第 2 步表明我无法证明我的假设，因为有 n 项。

我修改了证明的第2步

T(n) <= cn<sup>lg 3</sup> + n<sup>lg 3</sup>
      = (c+1)n<sup>lg 3</sup>

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

T(n) <= cn<sup>lg 3</sup>必须证明，而不是T(n) <= (c+1)n<sup>lg 3</sup>

但答案是T(n)是O(n<sup>lg 3</sup>)

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 项，从而使归纳成功。

希望这对您有所帮助!