アルゴリズムの学習を開始しました。のような「定期的な繰り返し」からシータ表記を見つける方法を理解していますT(n) = Tf(n) + g(n)。しかし、私はこの再発で迷っています: 問題 1-2e :
T(n) = T(√n) + Θ(lg lg n)
シータを見つける方法を選択するにはどうすればよいですか? で、えーと、この再発は何ですか？繰り返し内の表記法がよくわかりません。
10398 次
2 に答える
8
これは、変数置換を使用するのに最適な場所です。私たちはから始めます
T(n) = T(√n) + Θ(log log n)、
ここで、パラメータ n は平方根係数で減衰します。このような場合、うまく機能する一般的な変換は、S(m) = T(2 m ) を設定して新しい繰り返しを定義することです。ここでそれを行うと、次のようになります。
S(m) = T( 2m )
= T(√(2 m )) + Θ(log log 2 m )
= T(2 m/2 ) + Θ(log m)
= S(m / 2) + Θ(log m)。
言い換えれば、私たちは今、再発を持っています
S(m) = S(m / 2) + Θ(log m)。
物事を縮小する平方根の項がなくなったので、この再帰を扱うのはずっと簡単に思えます。特に、これはたまたまマスター定理が処理するものです。具体的には、a = 1、b = 2、d = 0 です (なぜ d = 0 なのですか? Θ(log m) は m 0 Θ(log m) と考えることができるからです)。マスター定理は、これが次のように解決することを示しています。
S(m) = Θ((log m) 2 )。
再帰 S(m) を解いたばかりですが、再帰 T(n) を解くことに興味がありました。それらをどのように接続しますか？S(m) = T(2 m ) なので、n が完全な 2 の累乗であると仮定すると、これを S(log n) = T(n) と書き換えることができます。それからそれを見ることができます
T(n) = S(log n)
= Θ((log log n) 2 ) ,
これが再発の解決策です。
于 2012-06-22T02:17:48.550 に答える
2
ここでは、数学を使用してそれを解決する方法を説明します。lnln(n)の代わりに使用しO(lnln(n))ます。これは主に式の長さを減らすためであり、big-O でもまったく同じことができます。そう：
つまり、次のことを意味します。
、
この大きな総和の通知を変換するには
全体のlnln(n)合計は次のように変換できます。
そして、私たちの唯一の問題は、最新の用語から簡単に導出できる とnの間の何らかの接続を見つけることです。kT(...)
これを行うには、最新の用語の合理的な境界条件を見つける必要があります。これは、 のような整数をいくつか試すことで実行できます0, 1, 2。あなた2が持っている：
k を前の式に代入すると、最大の項が次のようになることがわかります。
したがって、複雑さは次のとおりです。
PSここで同様の再発の解決策を見ることができます
于 2015-12-14T03:23:48.017 に答える