マスター定理では、ケース 1 で f(n) = O(log b of ae) の場合、ケース 1 と 3 があります。
マスター定理の 3 番目のケースでは、定数を追加する必要があります... なぜそうなるのでしょうか?
定数は何に基づいていますか？
1 に答える
2
このように考えるかもしれません - 例として 3 番目のケースを見てみましょう:
f(n) = O(n^(log(b a) + e)) for e < 0(ログは (a - e) ではなく、(a のベース b のログ) - e)
これはどういう意味ですか?
最初に 1 つのことを確立しましょう: 右側のブロブ全体 - O(n^(log(ba)))。これは、本質的に、T(n) 関数の f(n) 部分を考慮しない、関数の漸近的な動作です。
この部分は完全に直観的ではありませんが、考えてみれば正しいことがわかります。(f(n) = O(1) のいくつかの値を計算するだけで、私が正しいことがわかります。存在しない f(n) は、すべての意図と目的のために、O(1) であるためです。)
そのため、e を見てみましょう。e は何をしますか? それは確かにゼロよりも小さいです。これに課した制約のおかげで、e は方程式に入れると漸近的な「クラス」(n^2、log n など) を下げることを意味します。 . 言い換えれば、部分の漸近クラスを下げaT(n/b)て f(n) に等しくすることができれば、その意味aT(n/b)は f(n) よりも漸近的に大きくなり、それに応じて行動します。
これが何を意味し、マスターメソッドが何を意味するかは、O(T(n) - f(n)) = O(f(n)) を解くことです。
マスター メソッドが基づいている一般的な形式を見てみましょう
T(n) = aT(n/b) + f(n)
。aT(n/b)部分は、本質的にループです。何回反復するかを決定するもの。右の部分は、ループの本体です。実際に行った作業。右側が左側に対して漸近的に弱い場合、右側はそれほど重要ではなく、弱い、等しい、または大きい場合の漸近的な動作を決定するための素敵な式がいくつかあります。上で説明したように、e を減算または加算して、e が大きいか、小さいか、または等しいかを調べます。
この種のことを母国語ではなくテキストで説明するのは少し難しいですが、理解していただければ幸いです。
于 2010-05-05T21:19:40.983 に答える