なぜアルゴリズムの計算量オーダーにおいてlogが出てくるか？ - Qiita

はじめに 計算量オーダーについてlogだけにフォーカスした記事が無かったので執筆に至ります。 TL;DR アルゴリズムの計算では、**検索範囲 = 2^(探索回数)**という場面がある。 その対数を取れば log2 (検索範囲) = 探索回数 となるから。 なぜなのか アルゴリズムの計算量においてO(logn)のもっとも有名な例の一つである、二分探索の例を取ってみよう。 ざっくり二分探索について説明しよう。ニ分探索というのは、私達の生活にも無意識に使われている。 例えば私達が分厚い辞書から「121ページ目を開け」と言われた場合、 私達は、1000ページある辞書なら500ページ目から開き、次はその前半の半分250ページ目を開けるだろう。この繰り返しで121ページ目にたどり着く。 このような対象を二つに分ける探索、つまりこれがニ分探索である。 詳しくは アルゴリズムを勉強するなら二分探索から始