次の再帰関係を解決したいと思います。
T(n) = 2T(√n);
私はそれを推測してT(n) = O(log log n)いますが、これを証明する方法がわかりません。この再帰が に解決されることをどのように示しO(log log n)ますか?
22573 次
2 に答える
11
1 つのアイデアは、2 k = nとなるような新しい変数 k を導入して再帰を単純化することです。すると、再帰関係は次のようになります。
T(2 k ) = 2T(2 k/2 )
次に S(k) = T(2 k ) とすると、再帰が得られます。
S(k) = 2S(k / 2)
これは次と同等であることに注意してください
S(k) = 2S(k / 2) + O(1)
0 = O(1) なので。したがって、マスター定理によって、a = 2、b = 2、および d = 0 であり、log b a > dであるため、S(k) = Θ(k) が得られます。
S(k) = Θ(k) および S(k) = T(2 k ) = T(n) なので、T(n) = Θ(k) となります。2 k = n を選択したので、これは k = log n であることを意味し、T(n) = Θ(log n) となります。これは、O(log log n) の最初の推測が正しくなく、ランタイムが対数のみであり、二重対数ではないことを意味します。ただし、実行される再帰呼び出しが 1 つだけの場合、実行時間は O(log log n) になります。
お役に立てれば！
于 2013-11-05T01:02:31.557 に答える
5
これは、再帰を展開することで簡単に解決できます。
これで、繰り返しがいつ終了しT(1) = a、適切なa. いつa = 0または1それは意味がありませんが、いつa=2取得しますか:
kを最初の方程式の最新の部分に代入すると、 の複雑さが得られますO(log(n))。
ここで他の同様の再帰を確認してください：
于 2015-12-16T10:41:08.410 に答える