获得 karasuba 算法的复杂性？
get complexity for karasuba algorithm?
我看到 wiki 页面：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。当我在维基页面上阅读它时，T(n) 似乎适用于案例 1，但我们如何知道 cn (from T(n))，其中 c 小于 log_2(3) ？
T(n) = 3T(n/2) + cn + d
cn 中的 c 与用于主定理的 c 不同。主定理有 nc，这里的 cn 是线性的，其中 n 被提升到 1 次方，所以 c = 1。因为 c = 1 < log 23，适用第一种情况。
我看到 wiki 页面：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。当我在维基页面上阅读它时，T(n) 似乎适用于案例 1，但我们如何知道 cn (from T(n))，其中 c 小于 log_2(3) ？
T(n) = 3T(n/2) + cn + d
cn 中的 c 与用于主定理的 c 不同。主定理有 nc，这里的 cn 是线性的，其中 n 被提升到 1 次方，所以 c = 1。因为 c = 1 < log 23，适用第一种情况。