O記法で対数の底が省略される理由

プログラムにスピードを求めるなら多項式時間アルゴリズム、特に対数時間で解けるアルゴリズムが重要になる。なにしろ、Steven S. Skiena 氏がその著書 “The Algorithm Design Manual” で述べているように、Logarithm is an anagram of algorithm なのだ。

ところで、アルゴリズムの性能評価でお世話になる O 記法では、対数の底がしばしば省略される。たとえば、n 個のデータから二分探索で検索する場合、時間計算量は O(log2n) だが、これを O(log n) と表記することがある。

では、どうして、対数の底を省略するのだろうか？

恥ずかしながら、いままで「まあ、省略しても対数時間ということは分かるし、 そういうもんなんだろう」程度にしか考えていなかったが、書籍「アルゴリズムデザイン」に分かりやすい説明があった。

説明

まず、対数自体を忘れかけている自分自身のために、ものすごく基本的なところから。対数 logbn とは bx = n になる x に等しい数のことである。

そして、底の変換公式により、異なる底をもつ対数同士を相互に変換できる。

そして、右辺を変形すると：

ここで大事なのは、1/logba は定数になる、ということだ。

つまり、左辺と右辺では定数係数のみが異なることになる。O 記法においては定数係数は無視できるため、異なる底をもつ対数は等価とみなせる。よって、O 記法では対数の底がしばしば省略されるのである。

但し書き

最後に、ふたつばかり但し書きを。

書籍「アルゴリズムデザイン」では上記の説明を、最終的に：

となることから結論づけているが、O 以外の記号を導入するのが面倒だったので、この記事の説明では端折ってある。

また、使用している数式の画像は Formula という Web サービスを利用した。Formula は LaTex 形式で入力された数式の画像を生成し、簡単に貼りつけられるようにしてくれるサービスである（参考：Formula: 数式をブログに貼り付けて共有するサービス - Hello, world! - s21g）。