11

の場合、 C の値に依存するf(n)=O(g(n))べきではありませんか?f(n)∗log2(f(n)^c)=O(g(n)∗log2(g(n)))

ここで、C は正の定数です。私によると、Cが大きい場合、ステートメントはfalseになり、cが小さい場合はtrueになります。したがって、結果は c に依存します。

私はアルゴリズムのクラスを受講していますが、これは私が尋ねられた質問の 1 つです。私によると、これは定数 c に依存するはずですが、答えは間違っていました。

4

2 に答える 2

23 
log(x^c)  = c * log(x)

そう、

log2(f(n)^c) == c * log2(f(n))

したがって、

f(n)∗log2(f(n)^c) = c * f(n) * log2(f(n))

                   = O(g(n)∗log2(g(n)))
于 2013-01-30T06:40:56.580 に答える