アルゴリズム入門①計算量とソートの基本

はじめに

エンジニアであれば最低限知っておきたい「計算量」と「ソート(基本)」に関してまとめました。

続きはこちら
②実用的なソート
③探索
④再帰関数

計算量とは

アルゴリズムの演算の効率を評価するものであり、大きく空間計算量と時間計算量の二種類に分けられます。

• 時間計算量(どれくらい時間がかかるか)
• 空間計算量(どれくらい記憶領域が必要になるか)

両者のトレードオフを考慮した上でアルゴリズムを設計することが必要ですが、時間計算量の方が空間計算量の方よりも問題になることが多いです。

計算量の求め方に関しては以下の記事がおすすめです。

[初心者向け] プログラムの計算量を求める方法

計算量を求められるメリット

「レコードの増加に対して、どれくらい計算量が増加するか」を考えながらコードを書くことができるようになります。
　将来ユーザーが1万人になった時に計算量はどれくらい増加するか？などを考えることで、スケーラビリティの高いシステムを設計することができます。

次数ごとの計算量の限界

また時間計算量に関してはそれぞれの次数についてどれくらいの計算量になると、限界なのか知っておくと良いです。
線形の計算(O(N))においては、N=10^7~10^8が限界と覚えておくと良いと思います。¹
逆にいうと数が少ない場合N=100の場合はO(N^2)でも問題ないというわけです。

ソートとは

データの集合を一定の規則に従って並べることです。
例えば、整数の配列A=[2, 4, 5, 1, 3]を昇順にソートすると、[1, 2, 3, 4, 5]となります。

array = [2, 3, 4, 1, 5]
array.sort
# => [1, 2, 3, 4, 5]

一般的にアルゴリズムを設計・選択するときの重要なポイントはその計算量ですが、ソートのアルゴリズムに関しては「安定なソート」(後述)であるかも考慮に入れる必要があります。

つまり、ソートにおいては

1. 計算量(時間・空間)
2. 安定性

この二点に留意して、入力されるデータの特徴に対して、適切なアルゴリズムを選択する必要があります。

データの列を保持する一つの配列以外にメモリが必要になるソートを外部ソート、必要にならないソートを内部ソートといいます。

今回はソートのうち、効率は悪いですが、実装が簡単な基本的なソートアルゴリズムを紹介します。
クイックソートや、マージソートなどの効率がよく、実用的なソートアルゴリズムは②ソート(応用)で紹介します。

(捕捉)安定したソートとは

ソート前に同一のキーであったデータの順序関係がソート後にも変化しないもの

です。

例えば、学生番号順に並べられた学生を安定ソートによって身長順に並べた時、ソート後のデータにおいて、同じ身長の学生は学生番号順に並ぶようになっています。

隣り合うデータの比較処理を行う場合はその際にデータの前後関係の位置の保存が行われるので安定したソートとなり、
逆にクイックソートで見られるような離れた位置の要素との交換が行われる場合は前後関係は保存されず、不安定なソートとなります。

挿入ソート(Insertion Sorty)

以下のような手順でソートを行います。

1. 配列の先頭から一つ要素を取り出す。
2. 整列済みの配列に対して、先頭から要素の大小を比較しながら適切な位置に挿入する。
3. 元の配列が空になるまで1~2を繰り返す。

計算量は、最悪の場合$O(N^2)$となりますが、入力データがある程度整列されている場合は$O(N)$に近づき、非常に高速に動作するという特長を持ちます。
そのため「最初はクイックソートでソートし、ある程度整列されてから、挿入ソートに切り替える」という形で組み合わされて使われることもあります。

参考: バブルソート、選択ソート、挿入ソート

練習問題

Quick Sort - AIZU ONLINE JUDGE

バブルソート

以下のような手順でソートを行います。

1. 配列の末尾から隣接する二つの要素を取り出す。
2. 二つの要素の大小関係が逆ならば交換する。
3. 要素の交換が行われなくなる、または、N(N-1)/2回まで1~2を繰り返す。

計算量は最悪の場合は$O(N^2)$となります。

練習問題

Bubble Sort - AIZU ONLINE JUDGE

選択ソート

以下のような手順でソートを行います。

1. 元の配列から最小の要素を取り出す。
2. 整列済みの配列の末尾に追加する。
3. 元の配列が空になるまで1~2を繰り返す。

計算量は常に$O(N^2)$となります。
また安定なソートではありません。

練習問題

Selection Sort - AIZU ONLINE JUDGE

最後に

今回取り上げたソートはまとめると以下のような特徴があります。

ソート名	最良	最悪	安定
挿入ソート	$O(n)$	$O(n^2)$	○
バブルソート	$O(n)$	$O(n^2)$	○
選択ソート	$O(n^2)$	$O(n^2)$	×

どれも最悪の場合は、$O(n^2)$となりますが、特に選択ソートに関しては常に計算量が$O(n^2)$となるという特徴があります。

参考

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
コンピュータサイエンティストはソートアルゴリズムの中身を知るべきか

1. https://www.slideshare.net/catupper/ss-26238956 ↩