algorithm - f(n)=log n のマスターの定理

Question

マスターの定理では、次の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 の値に依存します。マスターの定理を使用して再帰関数を解くにはどうすればよいですか?

Answer 1

通常、マスター定理が適用されるには、f(n) は多項式でなければなりません。すべての関数に適用されるわけではありません。ただし、マスター定理には限定された「第 4 のケース」があり、多対数関数に適用できます。

f (n) = O(n ^{log _b a} log ^k n) の場合、 T(n) = O(n ^{log _b a} log ^k+1 n) です。

つまり、T(n) = 2T (n/2) + n log n があるとします。f(n) は多項式ではありませんが、f(n)=n log n、k = 1 です。したがって、T(n) = O(n log ² n)

詳細については、このハンドアウトを参照してください: http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-HandoutNoNotes.pdf

Answer 2

マスター定理に関するウィキペディアの記事から、これらの 3 つのケースがもう少し有用であることがわかるかもしれません。

• ケース 1: f(n) = Θ(n ^c )、c < log _b a
• ケース 2: f(n) = Θ(n ^c log ^k n)、c = log _b a
• ケース 3: f(n) = Θ(n ^c )、c > log _b a

現在、n の選択に直接依存することはなくなりました。重要なのは、f の長期的な成長率と、それが定数 a および b にどのように関係しているかだけです。あなたが解決しようとしている特定の再発の詳細を確認しない限り、これ以上具体的なアドバイスを提供することはできません.

お役に立てれば！

Answer 3

f(n)=log(n) の場合、マスター定理は適用されません。より一般化された定理Akra–Bazziを使用する必要があります。

その結果、Ｔ（ｎ）＝Ｏ（ｎ）となる。

ソース。

この結果のより具体的な証拠を見つける別の方法は、「最適な並べ替え行列検索」アルゴリズムの計算の複雑さの証明を探すことです。