計算の複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/08/02 06:48 UTC 版)
二進対数は、アルゴリズム解析で頻出する。1より大きな数 n を2で繰り返し割っていき、その値を1以下にするために必要な繰り返し回数は、 ⌊ lb n ⌋ {\displaystyle \lfloor \operatorname {lb} \,n\rfloor } で与えられる。この発想は、多くのアルゴリズムやデータ構造の分析で使用される。例えば二分検索では、検索すべき空間の大きさは操作の繰り返しごとに半分になる。ゆえに、大きさ1の問題を得るには大まかにいって lb n 回の繰り返しが必要となり、そのあとは定数時間で終了する。同様に、n 個の要素からなる完全平衡二分探索木は、1 + lb n の高さをもつ。 しかし、アルゴリズムの実行時間は通常、定数倍の差を無視してランダウの記号で表記される。ここで、1以外の任意の正の数 k に対して log2 n = logk n / logk 2（底の変換）が成り立つので、O(log2 n) の実行時間をもつアルゴリズムは、1より大きな任意の底、たとえば13を用いて、O(log13 n) の実行時間を持つとも表現できる。したがって、O(log n) や O(n log n) といった式では、対数の底がいくつであるかは本質的な問題ではない。 ただし、対数の底を指定する必要があるケースもあるので注意が必要である。例えば、所要時間 O(2lb n) の計算と、所要時間 O(2ln n) の計算とは同等ではない。前者は O(n) と等価であり、後者は O(n0.6931...) と等価である。 O(n log n) の実行時間をもつアルゴリズムは、しばしば線形対数と呼ばれる。O(log n) や O(n log n) の実行時間をもつアルゴリズムの例としては、次のようなものがある。 クイックソート（ただしこれは平均の場合であり、最悪の場合には O(n2) となる。） 2分探索木 マージソート モンジュ配列（英語版）の計算
※この「計算の複雑性」の解説は、「二進対数」の解説の一部です。
「計算の複雑性」を含む「二進対数」の記事については、「二進対数」の概要を参照ください。
- 計算の複雑性のページへのリンク
