分析複雜

Question

我被要求使用迭代方法來分析下面的遞歸公式的時間複雜度：

T（N）= T（N/3）+ T（2n個/ 3）+ N^2。

T（1）= 1

當我嘗試展開它炸燬方程，我真的不能跟蹤所有的遞歸「呼籲」和常量。 這是由於數據分割不均（1 \ 3 - 2 \ 3）造成的。

有沒有更簡單的方法來解決這個使用迭代方法？

非常感謝。

Answer 1

這似乎是爲O（n^2）如果我沒有錯過任何東西......

所有T首先單調增長（數第一值，您可以手動檢查這一點，它是由剩下的歸納 - 如果函數在[1..10]中單調，那麼它將在[1..15]等單調）。

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 

Answer 2

Here是紙示出一個類似的公式的分析：T（N）= T（N/3）+ T（2π/ 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 

..也許這可以給你一些提示

Answer 3

這裏有什麼有用的是不要乘以任何數字，而是用權力來寫所有的東西。這樣做，全部由手工，我得到了最初的幾個擴展如下：

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 

這是一個有點難以啓齒，但似乎什麼發生的是，你得到的二項式係數會爲T s，其中的x次擴張看起來是這樣的：

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

在每一步中，都在擴張x增加的附加常數是從擴張x-1的參數T，平方，因爲他們都最終獲得方感謝n^2。因此，所有的新常數在給定的擴張y等於：

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％確定的，我猜你必須弄清楚常數何時停止提供 - 也就是說，x是((2^x/3^x) * n)^2)等於0 - 你的答案是所有這些常數的總和。