algorithm - 如何计算 Karatsuba 算法的运行时间？

Question

我知道公式是 T(n)=3T(n/2)+O(n)，使用主方法我可以得到 T(n)=n^(log3)，以 2 为基数。

但是不使用master方法我仍然不知道如何得到答案。因为我从递归公式得到的结果是 T(n)=3^(logn) ，其中 2 是基数。

如果有人可以帮助我，我将不胜感激！

Answer 1

那是因为你们俩同时都是正确的。

n^(log3) = 3^(logn)

证明 ：

y = 3^log(n)
log(y) = log(n)*log(3)
log(y)/log(n) = log(3)

log<sub>n</sub>y = log(3)

y = n^(log3)