Help us understand the problem. What is going on with this article?

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

はじめに

計算量オーダーについてlogだけにフォーカスした記事が無かったので執筆に至ります。

TL;DR

アルゴリズムの計算では、検索範囲 = 2^(探索回数)という場面がある。
その対数を取れば log2 (検索範囲) = 探索回数 となるから。

なぜなのか

アルゴリズムの計算量においてO(logn)のもっとも有名な例の一つである、二分探索の例を取ってみよう。
ざっくり二分探索について説明しよう。ニ分探索というのは、私達の生活にも無意識に使われている。

例えば私達が分厚い辞書から「121ページ目を開け」と言われた場合、
私達は、1000ページある辞書なら500ページ目から開き、次はその前半の半分250ページ目を開けるだろう。この繰り返しで121ページ目にたどり着く。
このような対象を二つに分ける探索、つまりこれがニ分探索である。

詳しくは アルゴリズムを勉強するなら二分探索から始めよう! 『なっとく!アルゴリズム』より参照

実は、この二分探索の見方を変えると、x回探索をした場合2^xの範囲探索できるのです。

探索回数 検索範囲
1 2
2 4
3 8
4 16
5 32
6 64

表1 二分探索の探索回数と検索範囲の関係

つまり、探索回数と検索範囲の関係は検索範囲 = 2^(探索回数)と記述できます。
その対数を取ればlog2(検索範囲) = 探索回数 となるためlogが出現してくるのです。

ここで、探索回数というのは計算量オーダーであり、検索範囲というのはデータ数nであるため、
計算量オーダー = log2(n)となるわけです。

ここでlog2というのは底の変換公式で、(定数)log(n)という形に変換できる。
計算量オーダーにおいて定数は無視できるので一般的には
O(log(n))となるわけです。

以上のように、計算量オーダーのlogにおいて分からなくなる点が私的には二つあり、
なぜlogが出てくるのかというのと、なぜ底が2で無いのかというのがクリアになれば幸いです。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away