なぜコンピュータ科学の対数は2次対数であると推定されていますか？

Question

は、私は誰かがなぜ私に説明することができればそう、私は思っていた...

、コンピュータ科学の教科書で、次のを見ました。

Answer 1

コンピュータ科学で対数が生じる最も一般的な方法の1つは、バイナリ検索、マージソートなどの分割・征服アルゴリズムで頻繁に発生する配列を半分に分割することです。そのような場合、単一要素配列になる前に、長さnの配列を半分に分割することができます。ログはです。

対数が発生する別の非常に一般的な方法は、数値のビットを調べることです。バイナリで数値を書き出すには、数字nの場合、およそログ nビットを使用します。一度に1ビットずつ動作する基数ソートのようなアルゴリズムは、しばしばこれらのようなログを生成します。バイナリGCDアルゴリズムのような他のアルゴリズムは、2の累乗を除算することで動作するため、ログファクタが浮動することになります。

時間の関数として成長する連続的なプロセスで作業しているため、物理、数学、およびその他の科学の対数がしばしば発生します。自然対数は、ある種のプロセスの「自然な」成長率がe ^x（「自然」成長率の定義については）によってモデル化されているため、これらのコンテキストで発生します。しかし、コンピュータサイエンスでは、指数関数的な成長は、通常、上述の分割・征服アルゴリズムやバイナリ値の操作などの離散プロセスの結果として発生します。したがって、私たちは通常ログが頻繁に発生するので、対数関数としてログ nを使用します。

これは、CSで常に底2の対数を使用しているわけではありません。たとえば、AVLツリーの解析では、フィボナッチ数の存在のために、基底が黄の比率φである対数を使用することがよくあります。多くのランダム化されたアルゴリズムは、倍音数を含む自然な対数に戻るクイックソートの標準解析など、何らかの方法でeを含みます。これらは、成長率が何か他のもの（フィボナッチ数や指数関数）によってモデル化されているプロセスの例です。そこで、異なるログベースを選択します。バイナリ数値を使って作業するか、または基底2の対数がデフォルトになるように物を半分に分割することは十分に一般的です。

多くの場合、どのベースを選択しても問題ありません。たとえば、big-O表記法では、すべての対数は漸近的に等価であり（倍数定数だけが異なる）、O（n log n）やO（log n ）。