2

我被要求使用迭代方法分析以下递归方程的时间复杂度：

T(n)=T(n/3)+T(2n/3)+n^2。

T(1)=1

当我尝试扩展方程式时，它会爆炸，我无法真正跟踪所有递归“调用”和常量。这是由于数据的不均匀划分（1\3 - 2\3）造成的。

有没有更简单的方法可以使用迭代方法来解决这个问题？

非常感谢。

4

3 回答 3

0

It seems to be O(n^2) if I haven't missed anything...

First of all T grows monotonously (for several first values you can check this manually, for the rest it's by induction - if a function is monotonous in [1..10], then it will be monotonous on [1..15] and so on).

T(n)=T(n/3)+T(2n/3)+n^2<=2T(2n/3)+n^2
T(n)<=n^2+2*(2n/3)^2+4*(4n/9)^2+...
     =sum[k=0..log3(n)]((8/9)^k*n^2)
     =n^2*sum[k=0..log3(n)](8/9)^k
    <=n^2*sum[k=0..inf](8/9)^k
    <=C*n^2
于 2013-03-20T14:13:28.733 回答
0

这是一篇论文，展示了一个类似公式的分析：T(n)=T(n/3)+T(2n/3)+n

使其迭代的一种方法需要使用类似于解析器\编译器工作方式的方法

应用你的公式： T(n)=T(n/3)+T(2n/3)+n^2 与 n = 1..9 产量

T(0) = 0

T(1) = T(1/3) + T(2/3) + 1

T(2) = T(2/3) + T(4/3) + 4

T(3) = T(1) + T(2) + 9

T(4) = T(4/3) + T(8/3) + 16

T(5) = T(5/3) + T(10/3) + 25

T(6) = T(2) + T(4) + 36

T(7) = T(7/3) + T(14/3) + 49

T(8) = T(8/3) + T(16/3) + 64

T(9) = T(3) + T(6) + 91

T(3m) = T(m) + T(2m) + 9m^2

..也许这可以给你一些提示

于 2013-03-20T14:46:46.130 回答
0

这里有帮助的是不要将任何数字相乘，而是根据幂写出所有内容。全部手工完成后，我在前几次扩展中得到了以下信息：

T(n) = T((1/3)n) + T((2/3)n) + n^2
     =    T((1/3^2)n) 
       + 2T((2/3^2)n) 
       +  T((2^2/3^2)n) 
       + [n^2]                      #constants from the first expansion
       + [((1/3)n)^2 + ((2/3)n)^2]  #constants from the second expansion
     =    T((1/3^3)n) 
       + 3T((2/3^3)n) 
       + 3T((2^2/3^3)n) 
       +  T((2^3/3^3)n) 
       + [n^2] 
       + [((1/3)n)^2 + ((2/3)n)^2] 
       + [((1/3^2)n)^2 + ((2/3^2)n)^2 + ((2^2/3^2)n)^2] #constants from 3rd expansion

这有点难说，但似乎发生的是你得到了Ts 的二项式系数，其中xth 展开看起来像这样：

T(n) = sum((x choose i) * T(((2^i)/(3^x))n), i from 0 to x)
       + constants

在每一步中，在展开时添加的额外常量是from 展开x的参数，平方，因为它们最终都得到平方，这要归功于. 因此，给定展开式的所有新常数都等于：Tx-1n^2y

NewConsts(y) = sum(((y - 1) choose i) * (((2^i)/(3^(y-1)))*n)^2, i from 0 to y - 1)

并且所有展开时的常数x都等于

n^2 + sum(NewConsts(y), y from 1 to x)

所以，假设以上所有内容都是正确的，我不能 100% 确定，我想你必须弄清楚常数什么时候不再重要——也就是说，等于 0——x你((2^x / 3^x) * n)^2)的答案是所有的总和那些常数...

于 2013-03-20T15:14:56.077 回答