重复的运行时间是T(n)=3T(2n/3)+1多少，你是如何得到它的？
问问题
2748 次
2 回答
1
这种类型的递归可以用Master theorem解决。这里和。a=3_ 您的And 因为大于，所以您属于第一种情况。b=3/2f(n) = 1c = log1.5(3) = 2.709n^2.709f(n)
所以解决方案是O(n^2.709)
于 2015-12-15T08:23:17.673 回答
0
使用主定理。这比尝试自己解决重复问题要容易得多，就像您在原始问题中尝试的那样。
OTTOMH 这应该会帮助您T(n) = Theta(n^2.7)（主定理的案例 1）。
于 2013-02-19T14:34:26.740 回答