我正在尝试使用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)
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。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句