3

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

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

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

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

4

2 に答える 2

2

f(n) は Ω(nloga) に等しいため、ここで説明するマスター定理の 3 番目のケースを適用できます。

Here, 
f(n) = 2^n , and
Ω(n^log 1) = Ω(1)

2^n = Ω(1)、一部の定数 c>0 と十分な大きさのすべての n については、2^n ≥ c*1 であるためです。

したがって、T(n) = f(n)
T(n) = O(2^n)

于 2015-03-06T11:58:39.177 に答える