問題タブ [master-theorem]

私は中間試験を見て試験勉強をしようとしています。私が完全に理解していないことの 1 つは、マスター定理です。3つのケースがあることは理解しており、この形になっていれば適用できます

T(n) = 25T(n/5) + n^(2)

しかし、私の教授はこの形式でいくつかを与えるのが好きです

T(n) = {n+2 n=0,1,2,3の場合
T(n) = {4T(n-1) - 6T(n-2) + 4T(n-3) - T(n- 4) そうでなければ

そのため、Master Theorem を実行する別の方法がある場合、またはこれを何らかの方法で理解できる形式に変更することを意図している場合、私は混乱しています。

at(n) ∈ Θ(n^3/2) ランタイムでコードスニペットを作成する必要がある演習を解決しようとしています。

再帰、加算、減算、整数の 2 による除算、for ループ、if ステートメント、<、>、==、および if ステートメントと return ステートメントを使用できます。

t(n) ∈ Θ(n^3) のランタイムを取得するには、3 つの for ループを使用するだけで済みます。また、if ステートメントを使用すると、ランタイムが対数になるこのルールがあったと思います。t(n) ∈ Θ(n^3/2) のランタイムを取得する方法については、まったく考えがありません。

どなたかアドバイスいただけると本当に嬉しいです。ありがとう ：）

そのため、以前の試験で、マスター定理を使用せずに次の再帰方程式を解くように求められました。

残念ながら、私は試験でそれを理解することができなかったので、答えを知るためにマスターの定理を使って解いていました (しかし、もちろん、私はその問題の単位を取得しませんでした)。マスターの定理なしでそれを解決する方法を知っている必要があります。最終試験では同様の問題があるからです。

誰かが（説明付きで）段階的な解決策を提供できれば、それは素晴らしいことです、ありがとう！

(分割統治) trominoes アルゴリズムの複雑さとは何ですか?またその理由は何ですか?

2^k * 2^k サイズのボードが与えられましたが、タイルの 1 つがランダムに削除され、欠陥のあるボードになっています。タスクは、3 つのタイルで作られた L 字型の図形である「トロミノ」で埋めることです。

タイリングの問題

– 入力: n x n の正方形のボード。1 x 1 の正方形の 1 つが欠落しています。ここで、k ≥ 1 の場合は n = 2k です。

– 出力: トロミノを使用したボードのタイリング。2 x 2 の正方形から右上の 1 x 1 の角を削除した 3 つの正方形のタイル。

– ボードを並べるために、トロミノを回転させることができます。基本ケース: 2 x 2 の正方形を並べて表示できます。

誘導：

– 正方形を n/2 × n/2 の 4 に分割します。

– トロミノを「中央」に配置します。ここで、トロミノは、以前は 1 x 1 の正方形を逃していた n/2 x n/2 の正方形と重なりません。

– 4 つの n/2 x n/2 ボードのそれぞれを帰納的に解きます。

私は大学でアルゴリズムのコースを取っている学生です。単純な関数の実行コストを見つけるためにいくつかの再帰的手法を適用する方法を知っていますが、2^nこの質問では問題が発生しています。これが私がマスター定理を適用しようとしたものです

a=1、b=2 n^log2(1)= n^0.65

これはn^0=1、それが の多項式倍でなければならないことを知っていますが、f(N)これが2^nとどのように比較できるかわかりません2^n。

再帰ツリーも試しましたが、複雑になりすぎました。

次の再発を解決できません

私の仕事: マスター定理の適用

これはこれにつながり、n^0=1これはlと比較できませんog^2n

再帰ツリーも試しましたが、複雑になりすぎました。助けてください。

そのため、1 つではなく 2 つの再帰呼び出しがあるケースに遭遇しました。私は 1 回の再帰呼び出しを解決する方法を知っていますが、この場合、私が正しいか間違っているかはわかりません。

次の問題があります。

T(n) = T(2n/5) + T(3n/5) + n

そして、これの最悪の場合の複雑さを見つける必要があります。（参考までに-これはある種の拡張マージソートです）

私の感覚では、定理の最初の方程式を使用するつもりでしたが、私の考えには何か問題があるように感じます。このような問題を解決する方法についての説明をいただければ幸いです:)