MIT コースウェアと CLRS の本、アルゴリズム入門を使って勉強しています。
私は現在再発を解決しようとしています（107ページから）
T(n) = 2T(n/2) + n 4
再帰ツリーを作成すると、次のようになります。
レベル 0: n 4
レベル 1 2(n/2) 4
レベル 2 4(n/4) 4
レベル 3 8(n/8) 4
ツリーには lg(n) レベルがあります。したがって、再発はあるべきだと思います
T(n) = Θ(n 4 lg n)
でもマスター定理を使えばわかる
T(n) = Θ(n 4 )
明らかに、これらの両方が正しいとは言えません。どちらが正しいですか？そして、私の推論のどこが間違っていたのでしょうか?
2番目のものは正しいようです。再帰ツリーが次のようになっていることに注意してください
n 4 + 2(n/2) 4 + 4(n/4) 4 + ... + 2 i (n / 2 i ) 4
ただし、2(n/2) 4 ≠ n 4です。(n/2) 4 = n 4 / 16 なので、2(n/2) 4 = n 4 /8 です。実際、数学を解くと、レベル i で行われる作業は次の式で与えられることがわかります。
n 4 / (2 -3i )
したがって、(1 + 1/8 + 1/64 + 1/512 + ... ) n 4が得られ、これは 2n 4より小さいことが示されます。したがって、関数は Θ(n 4 ) です。
再帰では Θ(n^4) です
T(n) = 2*T(n/2) + n^4
T(n) = 2( 2*T(n/4) + (n/2)^4) + n^4 = 4*T(n/4) + 2*(n/2)^4 + n^4
T(n) = 4(2*T(n/8) + (n/4)^4) + 2*(n/2)^4 + n^4 = 8*T(n/8) + 4*(n/4)^4 + 2(n/2)^4 + n^4
T(n) = 8*T(n/8) + n^4*(1 + 1/(2^3) + 1/(2^6))
...
T(n) = 2^k*T(n/(2^k)) + n^4*(1+ 1/(2^3) + 1/(2^6) + 1/(2^9)...+ 1/((2^(k-1))^3)
We know T(1) = 1
n = 2^k so k = log2(n) Then
T(n) = n*T(1) + n^4*( 1 - (1/(2^3))^k)/(1-1/8)
T(n) = n + (8/7)*n^4*(1 - n^(-3))
T(n) = n + (8/7)*(n^4 - n)
T(n) = (8/7)*n^4 - (1/7)*n
Θ(T(n)) = Θ((8/7)*n^4 - (1/7)*n)
Θ(T(n)) = Θ(n^4)
Θ(n^4)です
ここでマスター定理を直接使用できます。
この式はマスター定理のケース 1 に適合します。log (a) base b < f( n)
a : 再発回数 b : サブパートの数
log a base b = log 2 base 2 = 1 < n^4
したがって、マスターの定理により、T(n) = theta(f(n)) = theta(n^4)