プログラミング

アルゴリズムの計算量

投稿日:2019年5月14日 更新日:

1. アルゴリズムの計算量

探索アルゴリズムやソートアルゴリズムを勉強すると、「計算量」という言葉が出てきます。

計算量を簡単に説明すると、

あるアルゴリズムにおいて、必要な命令数の規模を表した式

です。

もう少し説明を加えると、

処理対象となる値の数 \(n\) 個を十分大きくした場合に、必要な命令数がどれくらいの規模になるかを \(n\) を使って表した式

となるため、「\(n\) の増加に対する計算量の増加の程度を表す式」であるとも言えます。

アルゴリズム内における命令には、いろいろな種類があるはずですが、「\(n\) が十分大きい場合の命令数の規模」を考える場合は、「\(n\) の増加に伴って、一番増え方の程度が大きい命令の数」を考えればよいと考えます。それ以外の命令や、式にしたときの係数などは無視することができます。

ということで、計算量は「命令数の規模(増え方の規模)」ですが、実際には「計算に必要な時間」と捉えて考えることが多いです。

表記方法

この計算量を表記するには、

\(O(式)\)

という形で記述します。

※ \(O\) は order の頭文字で、Wikipedia には「程度」という意味だと書いてありますが、「次数」という意味でも良さそうです。

例えば、\(O(n) \) であれば、「オーダー \(n\) のアルゴリズム」と呼ぶことができます。

では、ランダウの記号 – Wikipedia に載っているアルゴリズム(一部だけですが)の計算量を見ていきます。 ※ クイックソートだけは独自に選びました。

2. \(O(1) \)

アルゴリズムの例:(整数の)偶奇判別

整数が偶数か奇数か判別する場合、対象となる1つ数について調べるだけなので、\(O(1)\) となります。

3. \(O(\log n) \)

アルゴリズムの例: ソート済み配列における二分探索

ソート済みの配列に対する二分探索というのは、

  1. 対象となる値全体を半分にする
  2. 目的の値が入っている方を、更に半分にする
  3. 目的の値が入っている方を、更に半分にする

を繰り返し、最終的に目的の値に到達するアルゴリズムです。

\(n\) 個の数に対して \(\frac{1}{2}\) → \(\frac{1}{2}\) → \(\frac{1}{2}\) → \(\frac{1}{2}\) と範囲を狭くするため、「\(n\) を \(k\) 回 \(\frac{1}{2}\) して、値を1つに絞る」と考えると、 \(n \times \frac{1}{ 2^{k}} = 1\) という式が書けます。これを変形すると \(n = 2^{k}\) となりますが、「2 を \(k\) 乗すると、 \(n\) になる」を対数で書くと \(\log_2 n = k \) です。\(\frac{1}{2}\) を実行した回数 k が、この場合の計算量であるので、\(O(\log_{2} n)\) と表すことができます。

4. \(O(n) \)

アルゴリズムの例: 非ソート配列上の探索

ソートされていない配列から目的の値を探すということなので、\(n\) 個の要素があるなら、\(n\) 個すべてをチェックしていくことになります。\(n\) 回の命令なので、計算量は \(O(n)\) です。

5. \(O(n \log n)\)

アルゴリズムの例: クイックソート

クイックソートは、おおまかに言うと 以下の操作を行うアルゴリズムです。

  1. ある数より大きいか小さいかで、\(n\) 個を2つのグループに分ける(このとき、\(n\) 個すべてにアクセスして判別処理する必要があります)。
  2. それぞれのグループに対して、同じ操作を行います。
  3. \(n\) 個すべての大小関係が決まるまで、この操作を繰り返します。

\(n\) 個が 1つになるまで、\(\frac{1}{2}\) する場合に必要な回数は、\(\log_2 n\) 。グループ分けする度に、各要素を判定しなければいけないので、グループ分けした階層毎に \(n\) 回の判定処理が必要。よって、以下の図から、計算量は \(O(n \times \log_2 n)\) となります。


※ この図は、[改訂新版]C言語による標準アルゴリズム事典 (Software Technology) に載っています(少なくとも、改定前のには載っていました)

6. \(O(n^2)\)

アルゴリズムの例: 挿入ソート

クイックソートは、\(n\) 個の数に対して 左端からソート済みのかたまりを作っていくアルゴリズムです。 (参照:挿入ソート – Wikipedia

  1. 左端から見て2つ目の要素から右端の要素まで順番に処理する。
    • \((n – 1)\)回の処理になる
  2. 1のループ処理内では、既にソート済の配列(最大 \((n – 1)\)個)を順番に見ていき、大小関係が成立する位置に現在処理対象の数を挿入する。

\((n – 1)\) 個の要素に対して、最大 \((n – 1)\) 個の中から位置を見つけるので、\((n – 1) \times (n – 1) = n^{2} -2n + 1\) となり、一番次数の大きい項だけ見ると、計算量は \(O(n^{2})\) となります。

7. 計算量のグラフ

取り上げた計算量をグラフにして比較します。

計算量の比較グラフ
計算量のグラフ

\(n\) の増加に対する計算量の増え方に注目してください。「\(n\) が増えても計算量がなるべく増えない」アルゴリズムが望まれます。

参考

📂-プログラミング

執筆者:labo


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

React Redux

React + Redux の最小限の雛形コード

ここに載せている JavaScriptのコードは、React + Redux を使っています。 但し、まだ何も意味のある処理を書いていないので、このままだと 属性 id=”root” を持った要素内に …

web development

Web Development for Beginners を読む:レッスン4と5

目次1. はじめに2. Lesson 4: JavaScript Basics: Data TypesVariables(変数)Constants(定数)Data Types3. Lesson 5: …

no image

ウェブプログラミングの知識があるとできること(その1)

先日、あるブログを見ていたら最新の記事だけが表示されない仕組みになっていました。 ウェブプログラミングの知識があるとこんなことができますという例として、その仕組を調べた時の過程を紹介します。 目次きっ …

web development

Web Development for Beginners を読む:レッスン12, 13, 14

目次1. はじめに2. Lesson 12: Browser Extension Project Part 1: All about BrowsersIntroductionAbout the bro …

Redux

Redux の非同期処理サンプルページを作りました

Redux で非同期処理を行うサンプルページを作りました。 目次1. スクリーンショット2. デモページ3. 動作4. ソースコード5. 参考情報 1. スクリーンショット スクリーンショット 2. …