50. 対数時間 O(logN) って思った以上に速い話

計算量で対数時間 $O(\log N)$ というものをよく見かけると思いますが、これが具体的にどの程度のものか、感覚で理解してみます。

まず大前提として、 $\log$ の底は（計算機科学においては一般に）2 です。何故 2 なのかというと、分割統治法の考え方で問題サイズを半分にすることを繰り返すことが多いからです。ここから計算回数 $\log_2 N$ という値が出てきます。

対数時間の感覚的な掴み方ですが、対数関数は指数関数の逆関数です。

指数関数 $y= n^x$ は（1より大きい自然数の底 $n$ を前提として）、 $x$ が増加するほど爆発的に $y$ が増加します。指数関数の爆発性は、「紙を $n$ 回折りたたむと高さ何メートルになるか？」といった例で有名です。

ここから考えて、逆に、対数関数 $y=\log_n x$ は $x$ が増加してもほとんど $y$ は増加しません。

具体的な値で考えてみます。競技プログラミングの文脈で、 $10^n$ ごとにどのような計算量になるかを調べたいです。

$y=\log_2 N$ を考えてみると、 $2^{10} =1024$ であることから、およそ $N=10^3$ で $y=10^1$ となります。たしかに速いですが、これだけではあまり速い印象が無いです。

そこで、次に $y=10^2$ となるときを考えてみます。高校数学を使うなり、計算するなりで確かめられますが、 $2^{100} \simeq 1.27 \times 10^{30}$ であることから、およそ $N=10^{30}$ でようやく $y=10^2$ となるのです。

すなわち、対数時間はほとんどの文脈で $\log N \simeq 10$ と考えられるわけです。ほぼ定数時間とみなして良いでしょう。よって、対数時間で解けるアルゴリズムはかなり強くなります。

対数関数の増加の緩やかさについて、 $2^{10^{n}}$ を書き下したなかなかとんでもないページを見つけたので紹介します。対数関数の出力を1桁増やすのに、これくらい大きな数が必要になるということです。

イバコの生存記録