algorithm - 如何计算算法时间复杂度

Question

我正在尝试将两个大整数与 Karatsuba 相乘算法。我知道 O(n) 是时间复杂度，T(n) 是最坏情况下的时间复杂度。

谁能解释一下原因:

T(n) = 4T(n/2) + O(n) is O(n^2)

和

T(n) = 3T(n/2) + O(n) is O(n^1.59)

Answer 1

T(n) = 4T(n/2) + O(n)

根据大师定理:

T(n) is O(n^log_2(4)) = O(n^2)

和

T(n) = 3T(n/2) + O(n)

是

T(n) = O(log_2(3)) ~ O(n^1,5849)

因此您可以将其四舍五入为 1.590。