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

Question

我知道这个公式是 T(n)=3T(n/2)+O(n)，通过使用主定理，我可以得到 T(n)=n^(log3)，其中底数为 2。

但是我仍然不知道如何在不使用主定理的情况下得出答案。因为我从递归公式中得到的结果是 T(n)=3^(logn)，其中底数为 2。

如果有人能帮助我，我将非常感激！

- Zoe Lee

---

嗨，@Zoe Lee，请在您认为答案解决了您的疑问时接受它。 - adisticated

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)

- adisticated

---

我简直不敢相信我花了整个早上才弄清楚为什么结果是3^logn。 - Zoe Lee