アルゴリズムの複雑さを対数で表す場合、たとえばマージ ソートは O(nlogn) です。
対数の底は何ですか?それは重要ですか?なぜですか?
質問する
104 次
2 に答える
3
対数の底は関係ありません。
次の方程式は、すべての m,n,k 1に対して成り立ちます。
log_m(n) = log_k(n)/log_k(m)
1/log_k(m)は定数であるため、 であるすべてのものもlog_k(n)ですlog_m(n)。これはすべての k,m に当てはまります。したがって、ビッグ O 表記を使用する場合、対数の底は問題になりません。O(log_k(n)) = O(log_m(n))
(1) 詳細: http://en.wikipedia.org/wiki/Logarithm#Change_of_base
于 2012-09-05T10:31:45.283 に答える
2
O 表記とオメガ表記では、異なる基数の定数を持つ対数は等価です。これは、差が定数であり、定数が無視されるためです。
見る。ビッグオー記法
于 2012-09-05T09:53:05.737 に答える