8

一般的な形式：T(n) = aT(n/b) + f(n)

したがって、n ^ logb（a）とf（n）を比較する必要があります

n^logba>がケース1f(n)であり、T(n)=Θ(n^logb(a))

n^logba<がケース2f(n)であり、T(n)=Θ((n^logb(a))(logb(a)))

あれは正しいですか？または私は何かを誤解しましたか？

そして、ケース3はどうですか？いつ適用されますか？

4

2 に答える 2

26

再発を解決するためのマスター定理

再発は、複雑な問題を解決する分割統治戦略で発生します。

それは何を解決しますか？

  • フォームの繰り返しを解決しT(n) = aT(n/b) + f(n)ます。
  • a1以上である必要があります。これは、問題が少なくとも1回は小さなサブ問題に縮小されることを意味します。少なくとも1回の再帰が必要です。
  • b1より大きくする必要があります。つまり、再帰ごとに、問題のサイズが小さいサイズに縮小されます。bが1より大きくない場合、それはサブ問題のサイズが小さいことを意味します。
  • f(n)の値が比較的大きい場合は、正である必要がありますn。

以下の画像を検討してください。

ここに画像の説明を入力してください

解決すべきサイズの問題があるとしましょうn。各ステップで、問題をサブ問題に分割できます。a各サブ問題のサイズは小さく、サイズは.1分の1に縮小されbます。

簡単な言葉での上記のステートメントは、サイズの問題が比較的小さいサイズのサブ問題にn分割できることを意味します。an/b

また、上の図は、問題を複数回分割した場合、各サブ問題が非常に小さいため、一定時間で解決できることを示しています。

以下の導出についてはlog、ベースを考慮してbください。

Hそれが木の高さだとしましょうH = logn。葉の数= a^logn。

  • レベル1で行われた総作業量：f(n)
  • レベル2で行われた総作業量：a * f(n/b)
  • レベル1で行われた総作業量：a * a * f(n/b2)
  • 最後のレベルで行われた総作業量：number of leaves * θ(1)。これは等しいn^loga

マスター定理の3つのケース

ケース1：

ここで、操作のコストが各レベルで大幅に増加し、リーフレベルに到達するまでに、の値がf(n)値よりも多項式的に小さくなると仮定しますn^loga。その場合、全体の実行時間は、最後のレベルのコストによって大きく左右されます。したがってT(n) = θ(n^loga)。

ケース2：

各レベルでの操作のコストはほぼ等しいと仮定します。その場合f(n)、はにほぼ等しくなりn^logaます。したがって、合計実行時間はf(n)、レベルの合計数の倍になります。

T(n) = θ(n^loga * logn)どこにありkますか>=0。lognのツリーの高さはどこになりますかk >= 0。

注：ここで、k+1はlognのログインのベースです。

ケース3：

各レベルでの操作のコストが各レベルで大幅に減少し、リーフレベルに到達するまでに、の値がf(n)値よりも多項式的に大きくなると仮定しますn^loga。その場合、全体の実行時間は、最初のレベルのコストによって大きく左右されます。したがってT(n) = θ(f(n))。

より詳細な読み物と実践例に興味がある場合は、私のブログエントリ「再発を解決するためのマスターメソッド」にアクセスしてください。

于 2015-06-19T20:36:06.213 に答える
5

あなたはそれを誤解していると思います。 n ^ logba> f（n）がケース1で、T（n）=Θ（n ^ logb（a））の場合

ここでは、結果としてf（n）について心配する必要はありません。得られるのは、T（n）=Θ（n ^ logb（a））です。f（n）はT（n）の一部であり、結果T（n）が得られた場合、その値にはf（n）が含まれます。したがって、その部分を考慮する必要はありません。

よくわからない場合はお知らせください。

于 2012-12-26T21:40:54.100 に答える