T(n)= 3T(n/2) + n^2 的时间复杂度是多少？
what is the time complexity of T(n)= 3T(n/2) + n^2?
我尝试使用递归树方法。
得到一个几何级数。
接下来是：
kn^2(1+ (3/2) +(3/2)^2 +...+(3/2)^b)
总和 = a(r^m -1)/r-1.
b = log n.
那怎么办我就懵了
你听说过Master's Theorem吗？您的示例是一个相对简单的子案例（没有对数）。结果是：
T = Theta(n^2)
我尝试使用递归树方法。 得到一个几何级数。 接下来是：
kn^2(1+ (3/2) +(3/2)^2 +...+(3/2)^b)
总和 = a(r^m -1)/r-1.
b = log n.
那怎么办我就懵了
你听说过Master's Theorem吗？您的示例是一个相对简单的子案例（没有对数）。结果是：
T = Theta(n^2)