algorithm - 递归替换证明中的大 theta 符号

Question

通常在 CLRS 中，当通过替换证明递归时，Ө(f(n)) 被替换为 cf(n)。

例如，在第 91 页，重复

T(n) = 3T(⌊n/4⌋) + Ө(n^2)

在证明中是这样写的

T(n) <= 3T(⌊n/4⌋) + cn^2

但是 Ө(n^2) 不能代表 cn^2 + n 吗？这不会使这样的证明无效吗？进一步在证明中，声明

T(n) <= (3/16)dn^2 + cn^2
<= dn^2

到达了。但如果使用 cn^2 +n 代替，则改为如下

T(n)<= (3/16)dn^2 + cn^2 + n

如果是这样，仍然可以证明 T(n) <= dn^2 吗？这样的低阶项在通过替换证明递归时无关紧要吗？

标签： algorithmsubstitutionrecurrenceproofclrs

Answer 1

是的，没关系。

T(n) <= (3/16)dn^2 + cn^2 + ndn^2如果 n 足够大，仍然小于或等于。因为随着 n 趋于无穷大，等式的两侧具有相同的增长率（即 n^2），因此如果成本函数中存在恒定数量的低阶项，则低阶项将永远无关紧要。但如果它们的数量不是恒定的，那就另当别论了。

编辑：当 n 趋于无穷时，您会发现合适的 d 和 cT(n) <= (3/16)dn^2 + cn^2 + n小于或等于dn^2，例如d = 2和c = 1