問題タブ [master-theorem]

最近、再帰について勉強しています。再帰と再帰は同じものだとしばらく考えていましたが、最近の宿題や小テストの問題で、「再帰」が方法であるというわずかな違いがあると思いました。再帰的なプログラムまたは関数を記述します。

問題やプログラムの「再帰」を記述するために使用される「マスター定理」と呼ばれるものがあることに最近気付くまで、これはすべて私にとって非常にギリシャ語でした。ウィキペディアのページを読んでいるのですが、いつものように、何を言っているのかよくわからないような言葉遣いで書かれています。私は例を使ってはるかによく学びます。

いくつかの質問があります: この繰り返しが与えられたとしましょう:

r(n) = 2*r(n-2) + r(n-1);
r(1) = r(2) = 1

これは実際、マスター定理の形をとっているのでしょうか? もしそうなら、それは言葉で何を言っているのですか？この再帰に基づいて小さなプログラムまたは再帰ツリーを作成しようとすると、どのようになりますか? 数値を代入してパターンを確認し、そのパターンを再帰的に作成できる疑似コードを作成するだけでよいでしょうか、それともマスター定理の形式である可能性があるため、より簡単な数学的アプローチはありますか?

ここで、前回の再帰から作成されたプログラムによって実行された追加の回数の再帰 T(n) を求めるよう求められたとします。基本ケースはおそらく T(1) = T(2) = 0 になることがわかりますが、そこからどこへ行くべきかわかりません。

基本的に、私は特定の繰り返しからコードに移行する方法とその逆を求めています。これはマスター定理のように見えるので、簡単で数学的な方法があるかどうか疑問に思っています。

編集：さて、過去の課題のいくつかを調べて、「再発を見つける」ように求められた別の例を見つけました。これは、投稿の問題を抱えているこの質問の一部です。

次のプログラム フラグメントの加算演算の数を最適な方法で記述する再帰 (l == 1 および r == n で呼び出した場合)

マスター定理では、ケース 1 で f(n) = O(log b of ae) の場合、ケース 1 と 3 があります。

マスター定理の 3 番目のケースでは、定数を追加する必要があります... なぜそうなるのでしょうか?

定数は何に基づいていますか？

中期的に私は問題を抱えていました：

そして、マスターまたは代替方法のいずれかを使用して、その大きなシータ表記を見つけることになっています。だから私がしたのは

a = 8、b = 2 k = 3

log ₂ 8 = 3 = k

したがって、T（n）は大きなシータn3^です。私は1/3ポイントを獲得したので、間違っているに違いありません。私は何を間違えましたか？

私はMITのオープンコースウェアのウェブサイトからいくつかのビデオ講義を見てきました。3番目の講義ビデオで、講師は再帰的行列乗算を調べ、時間計算量を考え出します。

T(n) = Θ(n3)

私は自分の数学のいくつかを本当に見直す必要があることは明らかですが、その答えとマスター定理法で言及されたケースのいずれかからの関連性は実際にはわかりません。漸化式の形式は次のとおり
T(n) = a*T(n/b) + f(n)です。n>1の場合。
この漸化式a = 8では、、、、b = 2および。f(n) = Θ(n2)

それで、彼らはどのようにして得ましたか？Θ(n3)

彼はそれを述べました、それは理にかなっています。しかし、の値を使用して、例の漸化式が3つのケースのどれに対応するかを理解することはできません。 log28 = 3f(n)

ケース2だけなので、f(n) = Θ(anything)それだけだと思います。それでも、私の問題は対数または指数の特性に関連していると思います。

もしそうなら、あなたはどのようにforを持つことからusing case 2に移行しますか？私がここで行方不明になっているのは何ですか？f(n) = Θ(nlog28 * (log2n)k+1)Θ(n3)f(n)Θ(n2)

漸化式

T（n）= 2T（n / 2）+ n lg lg n

（lgは2を底とする対数です）マスター定理を使用して解くことができますが、答えについてはよくわかりません。私は自分の答えを見つけましたが、情報のカスケードを防ぐためにここでは言及していません。上記の大きなOとΩを見つけるのを手伝ってください。

マスター定理を使用して、O()このステートメントに境界を設定します。

T(n) = 16T(n/4) + n2 + log n

私はマスター定理をますます理解しようとしており、オンラインでより多くの例を見つけてその解決策を得ようとしています。

= O(n2)マスター定理を使用。

上記は以下よりも複雑ですか？

どちらもマスター定理を使っていますが、定数の確認方法がわかりません。O(n2)

面白いと思いますが、解決策がわかりません。このアルゴリズムは x ^{nを計算します}

マスター定理を使用すると、私の推論は次のようになります

しかし、この場合の f(n) は 1 ですか? n <= 4 は定数であるためです。私に与えます：

置換を使用すると、この答えが得られます

私は多くのことを間違っていると思います。誰かが私を正しい方向に向けることができますか?

ここで、マスター定理がこの再帰関係のタイト バウンドを見つけるケースがどれなのか混乱しています。

T(n) = 27T(n/3) + Q(n ³ log n)

これが私の解決策です:
f(n) = n ³ log n
a=27 b = 3 so

したがって、ここでf(n) > n ³
であることがわかります 。

ケース 3 が適用されます。ここで間違っている場合は訂正してください。
注: しかし、答えは n ³ log ² n であり、これはマスター定理のケース 2 によるものです。どちらに申し込めばいいですか？

T（n）= 2T（n / 4）+1のようなケースがあるとします。f（n）= 1 a=2およびb=4。したがって、n ^（1/2）>1です。これはケース1である必要があります。ただし、ケース1にはラムダもあるため、ラムダ> 0の場合はf（n）= O（n ^（（1/2）-lambda））になります。この場合、ラムダは1/2になりますか？