「指数は対数に勝る」と言われました。
しかし、指数関数が 0 と 1 の間にある場合、対数の実行時間ははるかに速くなりませんか? したがって、その論理では、f = O(g) になります。
直感に従うか、言われたことに従うかで迷っていますが、言われたことは完全に正確ではなかった可能性があります。
3184 次
3 に答える
3
ここで数学を試してみましょう。1 つの重要な事実は、対数関数が単調増加することです。つまり、
log f(x) ≤ log g(x)
それから
f(x) ≤ g(x)
では、ここで何をするか見てみましょう。x 0.1と log 10 xの 2 つの関数があります。彼らのログを取ると、
ログ (x 0.1 ) = 0.1 ログ x
と
ログ (ログ10 x) = 10 ログ ログ x
log log x は log x よりもはるかにゆっくりと成長するため、関数 x 0.1が最終的に log 10 xを追い越すことが直感的にわかります。
では、これを公式化してみましょう。となるような x の値を見つけたいとします。
x 0.1 > ログ10 x
計算を簡単にするために、これらが 10 を底とする対数であると仮定しましょう。ある k に対して x = 10 kと仮定すると、次のようになります。
(10 k ) 0.1 ≥ log 10 10 k
10 0.1 k > ログ10 10 k
10 0.1 k > k
ここで、k = 100 を取ります。
10 0.1 * 100 > 100
10 10 > 100
これは明らかに真実です。両方の関数が単調増加するため、これは x ≥ 10 100の場合、次が真であることを意味します。
x 0.1 > ログ10 x
つまり、x 0.1 = O(log 10 k)ではないということです。
お役に立てれば！
于 2011-09-08T03:02:29.637 に答える
1
漸近分析は実際には長期的な関係に焦点を当てています (n はより大きな値を想定しているため、関数の値はどのように比較されますか)。また、定数を無視するため、f(x) = 10000000*x = O(x^2) のような奇妙な状況が時々見られます。
の値が大きい場合n、f(n) > g(n)これだけが重要です。
于 2011-09-08T03:34:00.863 に答える