LoginSignup
2

More than 5 years have passed since last update.

バイナリサーチの計算量がO(log_2 n)となる理由

Last updated at Posted at 2016-11-18

データ個数が$n$の時のバイナリサーチの計算量が$O(log_2n)$となる理由について書いてみました。

$log_an$ とは「$a$を○乗すると$n$になる」の「○」にあたる値です。
(例:$log_28$ は「$2$を○乗すると$8$になるような○」なので「$log_28 = 3$」)

バイナリサーチのアルゴリズムを簡単に書くと

  1. 検索範囲(ソート済み)の中央に位置する値を検索値と比較する。
  2. 検索値が中央の値より大きければ中央より右側、小さければ中央より左側を検索範囲に設定する。
  3. 中央の値 == 検索値が真となるような中央の値が見つかる(または検索範囲が$1$になる)まで、1~2を繰り返す

…となります。

検索範囲が$1$になった状態とは、(検索範囲のデータ個数を$n$として)「$n$に対して$\frac{1}{2}$を繰り返し掛けていき、検索範囲のデータ個数が$1$になった状態」と言えますが、これを数式で表現すると以下のような式となります。

\begin{align}
1 &= n \times \frac{1}{2} \times \frac{1}{2} \times\quad...\quad\times \frac{1}{2}\\
\end{align}

上の式において、「$n$に対して$\frac{1}{2}$を掛ける回数」が、データ個数が$n$の時の計算量となります。この「$\frac{1}{2}$を掛ける回数」を$x$とし、式変形して$x$を求めていきます。

\begin{align}
1 &= n \times \frac{1}{2} \times \frac{1}{2} \times\quad...\quad\times \frac{1}{2}\\
&= n \times \Bigl(\frac{1}{2}\Bigr)^x\\
&= n \times \frac{1}{2^x}\\
&= \frac{n}{2^x}\\
両辺に2^xを掛けると\\
2^x &= n\\
\therefore x &= log_2n
\end{align}

以上、データ個数が$n$の時のバイナリサーチの計算量が$O(log_2n)$となる理由でした。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2