二進対数 - Wikipedia

よく計算量のオーダーででてくる二進対数について。

二進対数 (にしんたいすう、英: binary logarithm)とは、2を底とする対数 log2 x のことである。これは、指数関数 x → 2x の逆関数でもある。

しかし、アルゴリズムの実行時間は通常、定数倍の差を無視してランダウの記号で表記される。ここで、1以外の任意の正の数 k に対して log2 n = logk n / logk 2（底の変換）が成り立つので、O(log2 n) の実行時間をもつアルゴリズムは、1より大きな任意の底、たとえば13を用いて、O(log13 n) の実行時間を持つとも表現できる。したがって、O(log n) や O(n log n) といった式では、対数の底がいくつであるかは本質的な問題ではない。

なるほど、計算量の対数の底ってなんだ？ってなることあるけどランダウの記号が定数倍の差を無視するから記述されないわけだ。

ランダウの記号 - Wikipedia

変数 x が 2 より大きければ第一項 3x2 が他の項より大きく、さらに大きくなるほど支配的になることがわかる。漸近解析をする上では定数倍のような詳細は必要としないことが多く

記法 名称 アルゴリズムの例
O(1) 定数時間 (Constant time) （整数の）偶奇判別
O(log n) 対数 (logarithmic) ソート済み配列における二分探索
O(n) 線形関数 (linear) 非ソート配列上の探索、離散ウェーブレット変換
O(n log n) 準線形、線形対数 (linearithmic, loglinear, or quasilinear) ヒープソート、高速フーリエ変換
O(n2) 二乗時間 (quadratic) 挿入ソート、離散フーリエ変換
O(2n) 指数時間 (exponential, geometricとも) （現在最も速い）巡回セールスマン問題の（厳密解の）解法
O(n!) 階乗関数 (factorial, combinatorialとも) 2つの論理式の同型判定[1]、巡回セールスマン問題の（可能）解の枚挙