問題タブ [master-theorem]

私はMaster Theoremを少し更新していますn.2つのサイズのサブ問題を再帰的に解決n-1し、ソリューションを一定時間で結合することにより、サイズの問題を解決するアルゴリズムの実行時間を把握しようとしています.
式は次のとおりです。
T(N) = 2T(N - 1) + O(1)
しかし、マスター定理の条件をどのように定式化できるかわかりません。つまり、この場合のマスター定理の式は
ありませんか? はいの場合、明らかにそれ以降であり、これをどのように理解できるかのベースはどこにありますか? 私がこれまでのところ正しいと仮定しますか？T(N/b)bb=N/(N-1)
a > b^kk=0O(N^z)z=log2(N/N-1)

再帰関係を解決する方法についていくつか問題があります。

T(n) = T(n/2) + log2(n)、T(1) = 1、n は 2 の累乗

これは宿題なので、ただ答えを教えてはいけません。問題をどのように開始するのか疑問に思っていました。

クラスでは、マスター定理について説明しました。しかし、それがこの特定の関係を解決する最善の方法だとは思いません。

問題を開始する方法がよくわかりません... ただ行くべきですか

そして、私が見ることができる何かを得るために私の道を進み続けて、基本的な方程式を作りますか?

これは宿題です。

配列のモード (正の値) を見つけ、モードがsizeof(array)/2支配的な値より大きい場合は、その値を二次的に返す必要があります。一部の配列にはどちらもありません。これは簡単ですが、決定の前に配列をソートしてはならないという制約があり、さらに、複雑さは O(nlogn) のオーダーでなければなりません。

この 2 番目の制約とマスター定理を使用して、時間計算量 'T(n) = A*T(n/B) + n^D' を決定できます。ここで、A=B および log_B(A)=D for O(nlogn ） 真であります。したがって、A=B=D=2 です。ドミナント値は、配列の前半、後半、または両方でドミナントでなければならないため、これも便利です。

'T(n) = A*T(n/B) + n^D' を使用すると、検索関数が各レベル (A) で 2 回自身を呼び出し、各レベル (B) で問題セットを 2 で分割することがわかります。アルゴリズムが各レベルで n^2 を考慮に入れる方法を考え出すのに行き詰まっています。

これのいくつかのコードを作成するには：

ここで欠けている「接着剤」は、これらの分割された機能を組み合わせる方法であり、n^2 の複雑さを実装すると思います。ここには、前半または後半、またはその両方でドミナントがドミナントでなければならないいくつかのトリックがありますが、複雑さの制約で今それがどのように役立つかはよくわかりません.

小さな配列の例をいくつか書き留め、それが分割される方法を示しました。常に優勢な値を返す単一のメソッドを見つけるという正しい方向に進むことができないようです。

レベル 0 では、関数は自分自身を呼び出して配列の前半と後半を検索する必要があります。それは再帰して、それ自体を呼び出す必要があります。次に、各レベルで n^2 操作を実行する必要があります。したがって、配列 [2,0,2,0,2] では、それを [2,0] での検索と [2,0,2] での検索に分割し、さらに 25 回の操作を実行します。[2,0] の検索は、[2] の検索と [0] の検索を呼び出し、4 つの操作を実行します。これらは配列空間自体の検索である必要があると思います。私は C++ を使用し、STL から何かを使用して値を繰り返しカウントすることを計画していました。大きな配列を作成し、そのインデックスでカウントを更新するだけです。

したがって、問題は、x が行ごとおよび列ごとに昇順で並べ替えられた行列の要素の 1 つに含まれているかどうかを調べることです。

例 ：

1 2 3

4 5 6

7 8 9

この問題の分割統治法による解決策の時間計算量を見つけることに興味があります。私はそれをグーグルで検索しましたが、O(m+n) ソリューションのみを見つけました。また、このSearch a sorted 2D matrixからも見つかりました。しかし、彼は「T（R）= 3T（R / 4）」と（回答のコメント）言っていますが、なぜf（R）= 0なのですか？

問題は、マスター定理を使用した分割統治法ソリューションの複雑さは何ですか? T(R) = 3T(R/4) + f(R) では、f(R) はどうあるべきですか?

それが役立つ場合、これは私の分割統治ソリューションです：

解決策を明確にするために編集：

アルゴリズム : 1. 行列の中央の要素を検索値と比較します 2. 値が m(i,j) と等しい場合は true を返します 3. 値が小さい場合、値の右上、左上、左下を検索します行列 4. 値が大きい場合は、行列の右上、右下、左下の値を検索します

私は再発関係を持っています、それは次のようなものです：

T(e ⁿ ) = 2(T(en ^-1 )) + e ⁿ、ここで e は自然対数です。

これを解決して Θ 境界を見つけるために、次のことを試しました: k=e ⁿを入力すると、方程式は次のように変換されます。

T(k)=2T(k/e)+k

次に、マスター定理を使用してみます。マスター定理によれば、a=2、b=e>2、f(k)=k です。したがって、いくつかの ε>0 に対して f(k)=Ω(n ^{log _b a+ε} ) の場合があるため、T(k)=Θ(f(k))=Θ(k) となります。次に k=n とすると、T(n)=Θ(n) となります。私のソリューションに間違いはありますか？

クイズでこれを持っていた：T（n）= 4T（sqrt（n））+ 5

置換を使用して簡略化し、F（k）= 4F（k / 2）+5を取得しました

マスター定理を使用して、私はそれがO（logn）であると推測しました。これは正確ですか？

マスターの定理では、次のT(n) = a*T(n/b) + f(n)3 つのケースを使用しています。

1. a*f(n/b) = c*f(n)ある一定c > 1の場合T(n) = (n^log(b) a)
2. もしそうa*f(n/b) = f(n)ならT(n) = (f(n) log(b) n)
3. a*f(n/b) = c*f(n)ある一定c < 1の場合T(n) = (f(n))

しかし、f(n) = log nまたはの場合n*log n、 の値cは n の値に依存します。マスターの定理を使用して再帰関数を解くにはどうすればよいですか?

マスター定理を使用して再帰関係を解決しました。Θ(3n ² -9n)まで下げました。これはΘ(n ² )に等しいでしょうか? 解決策がΘ(2n ³ - 100 ² )である別の再発があります。BigTheta 表記では、常に最大の項のみを使用しますか? 2 つ目はΘ(n ³ )ですか? 2 番目のケースでは100n ²の方が重要なようです。では、捨てても問題ないでしょうか？

助言がありますか？

マスター定理をどのように理解するか、アルゴリズムは次のように再帰的に定義できます。

ここで、a は部分問題の数、n/b は部分問題のサイズ、O(n^d) は部分問題の再結合時間です。マスター定理の時間計算量を計算すると、次のようになります。

私の質問は、再結合時間が O(n^d) の形式で表現されていない場合はどうなるでしょうか? O(2^n) や O(log(n)) など。時間の複雑さをどのように決定しますか?

Mergesort から複雑さを計算しようとしています。標準のマージソートには再帰 T(n) = T(n/2)+T(n/2)+n があるため、マスター定理で簡単に計算できます。

しかし、私の質問は、 T(n) = T(2n/3) + T(n/3) + n および T(n) = T(n-100) + T(100) で Mergesort を計算する方法ですか?

みんな助けてくれませんか？ありがとう =)