ソートアルゴリズムで見るプログラムの計算量

はじめに

はじめまして。開発エンジニアのCarboxyです。
ラクスに新卒で入社して、今年で２年目になります。

今回は、新卒（≒エンジニア初心者）が、効率の良いプログラムを書けるようになるきっかけになればと思い、プログラムの計算量の求め方とその比較方法をソートアルゴリズム（選択ソート）を例に紹介します。

計算量とは

ある問題を解くためにどのくらい計算が必要かどうか（どのくらい時間がかかるか）

→アルゴリズムの性能評価に使用できる。

O(オーダー)記法を用いて示す。
※計算量には時間計算量と空間計算量があるが、この記事では時間計算量の事を指す。

O(オーダ）記法

計算量の一般的な記述方法。大まかな時間計算量を表す。
例として、入力サイズ n の関数として表される時間計算量T(n)が

$T_{(n)} = 10n^2 + 100n + 1000$

で与えられる場合、オーダー記法では最も次数の高い項の係数を省いて

$O(n^2)$

となる。なぜこのように最も次数の高い項（主要項）の係数を省くような、漸近的な評価が使われるかというと、入力サイズ n が十分に大きい場合は、時間計算量は主要項にのみ依存するからである。

選択ソート

選択ソートを例に計算量を考える。
選択ソートは最も基本的なソートアルゴリズムの１つで、次のようなアイデアに基づきソートを行っていく。

1,入力データの中から最大のデータを見つける。
2,見つけた最大のデータをソートの対象から除外する。
3, 1と2 の操作を n - 1 回繰り返す。

ソースコード

入力サイズ n の配列 D[0]、D[1]、・・・、D[n-1]

for (i=n-1; i>0; i=i-1) {
  max = D[0];
  maxIndex = 0;
  for (j=1; j<=i; j=j+1) {
    if(D[j]>=max) {
      max = D[j];
      maxIndex = j;
    }
  }
  swap(D[maxIndex],D[i]);
}

このアルゴリズムは、２重のfor文により構成されている。変数 n に依存する i , j の２重ループなのだからO(n^2)になることは安易に想像できるが、計算すると次のようになる。

外側のfor文の繰り返し実行回数は n - 1 回であり、内側のfor文は外側のfor文の変数 i に依存し、i 回の繰り返しとなっている。したがって、このアルゴリズムの計算量は、以下の式で表される。

$O(1) × \sum_{i=1}^{n-1}i$

$=O(1) × \{1 + 2 + 3 + ... + (n-1)\}$

$=O(1) × \frac{n(n - 1)}{2}$

$=O(n^2)$

計算量の比較

複雑になるため詳細は省略するが、その他のソートアルゴリズムの計算量を計算すると、例えばクイックソートの場合はO(n logn)になる。オーダー記法の漸近的な大小関係は以下のようになることから、選択ソートとクイックソートを比較するとクイックソートのほうが計算量が小さい事が数値的にわかる。

$log n ＜ \sqrt{n} ＜ n ＜ n log n ＜ n^2 ＜ n^3 ＜ ... ＜ 2^n ＜n!$

まとめ

オーダ記法によって漸近的な時間計算量を示すことができる。
プログラムを実行して時間を測定しなくとも、入力サイズ n に対してどのアルゴリズムが一番速いか数値的に比較できる。

RAKUS Developers Blog | ラクスエンジニアブログ

株式会社ラクスのITエンジニアによる技術ブログです。