根据主定理,这个递归是 θ(n^2),但是如果我们用树递归来解决这个问题,那么解就是 θ(n^2*logn)。难道我做错了什么?
如果递推关系为 T(n) = 2T(n/2) + n^2,那么您处于主定理的第三种情况,并且正则性条件适用,因此 T(n) = Theta(n^ 2)。 [c_crit 为 log_2(2) = 1, n^2 = Omega(n), 2(n/2)^2 = (n^2)/2 (因此 k
如果你手动展开递推关系,那么你会得到:
T(n) = n^2 + 2(n/2)^2 + 4(n/4)^2 + 8(n/8)^2 + ...
= n^2 ( 1 + 1/2 + 1/4 + 1/8 + ...)
<= 2n^2
所以这个方法也给你 T(n) = Theta(n^2)。
方法为将递推关系输入 Wolfram Alpha 并查看其内容 https://www.wolframalpha.com/input/?i=T%28n%29%20%3D%202T%28n%2F2%29%20%2B%20n%5E2给出 T(n) ~ 2n^2,所以又是 Theta(n^2)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)