2

反復法を使用して、次の再帰方程式の時間計算量を分析するように依頼されました。

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

T(1)=1

方程式を拡張しようとすると、爆発し、すべての再帰的な「呼び出し」と定数を実際に追跡できなくなります。これは、データの不均等な分割 (1\3 - 2\3) が原因です。

反復法を使用してこれを解決する簡単な方法はありますか?

どうもありがとう。

4

3 に答える 3

0

これは、同様の式の分析を示す論文です：T（n）= T（n / 3）+ T（2n / 3）+ n

反復処理を行う1つの方法では、パーサー/コンパイラーの動作と同様の方法を使用する必要があります。

式を適用すると、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

T見分けるのは少し難しいですが、どうやらs の二項係数が得られるようです。ここで、 xth 展開は次のようになります。

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

各ステップで、展開時に追加される追加の定数はfrom Expansionxの引数である squaredです。したがって、特定の展開でのすべての新しい定数は次のようになります。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％確信が持てませんが、定数がいつ重要でなくなるかを把握する必要があると思います-つまり、 0xに((2^x / 3^x) * n)^2)等しいものについて-そしてあなたの答えはすべての合計ですそれらの定数の...

于 2013-03-20T15:14:56.077 に答える
0

何も見逃していなければ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
于 2013-03-20T14:13:28.733 に答える