algorithm - 得到 karatsuba 算法的复杂性？

Question

我看到了维基页面:https://en.wikipedia.org/wiki/Karatsuba_algorithm karatsuba 算法的递归关系为:

T(n) = 3T(n/2) + cn + d

通过master算法，其时间复杂度为T(n) = O(n^log_2(3))。我以前从未使用过 master theorem。当我在 wiki 页面上阅读它时，似乎 T(n) 适用于案例 1，但我们如何知道 cn (from T(n)) , 其中 c 小于 log_2(3)?

Answer 1

T(n) = 3T(n/2) + cn + d

cn 中的

c 与您用于主定理的 c 不同。大定理有 n^c，这里的 cn 是线性的，其中 n 被提升到 1 次方，所以 c = 1。因为 c = 1 < log₂3，适用第一种情况。