アルゴリズムにおける計算量とは!? 6種類の基本ソートで計算量比較

プログラムを高速に動作させるには、入力値を効率良く制御できるアルゴリズムを考える必要があるので、今回は基本的なソートアルゴリズムを実装して計算量Oを確認。

またアルゴリズムでは2つの観点(時間+領域)から計算量を評価。

TaNA
一般的に時間計算量と領域計算量はトレードオフの関係と言われますが、以前に比べてハードウェアが進化しているので、領域計算量より時間計算量を重視する傾向が高いでしょうか。普段領域計算量はほぼ考慮出来ていないかも…

また単に計算量(オーダー)と言う場合、時間計算量を指すのが一般的な模様。

今回確認する基本的なソートプログラムは以下書籍から抜粋していますが、本書がC++で解説されているので、興味があってC++分かる方は是非一読頂ければとmm

バブルソート.

配列の末尾から隣接要素の大小を比較し、大小関係が逆ならば並び替えを行うソートアルゴリズム。

バブルソートの計算量は $O(n^2)$ となります。

データ数nが小さければ良いですが、計算量はデータ数の二乗に比例するので注意が必要。

挿入ソート.

挿入ソートは未ソート部分とソート済み部分に分けて処理するアルゴリズム。

バブルソート同様に比較回数は$(n^2 – b)/2$ 回なので、アルゴリズムの計算量 $O(n^2)$となります。

初期の並び順に依存するので、降順気味に並んでいると $O(n^2)$、昇順だと $O(n)$ に近づく。

選択ソート.

選択ソートは未ソート部分とソート済み部分に分けて処理するアルゴリズム。

バブル・挿入同様に比較回数は$(n^2 – b)/2$ 回なので、アルゴリズムの計算量 $O(n^2)$となります。

シェルソート.

シェルソートは、ほぼ整列された集合に高速に動作する挿入ソートの特徴を活かしたアルゴリズム。

シェルソートでは、ある一定間隔gだけ離れた要素のみを対象とした挿入ソートを繰り返す。

間隔gの取り方で計算量が異なり、上の例では計算量 $O(n^{1.25})$ になると予測されます。

マージソート.

バブル・挿入・選択ソートなどの初等アルゴリズムでは大量データに不向き。

そこで大量のデータにも耐えうるアルゴリズムの一つがマージソート。

マージソートでは分割 + 再帰 + 統合の3ステップで計算量 $O(nlogn)$ を実現。

例えばデータ{9, 6, 7, 2, 5, 1, 8, 4, 2}の1個のデータになるまで分割。

9 → 5 → 3 → 2 → 1の4分割が必要となり、出来上がる階層は5階層。

n個のデータに対しておおよそlogn個の階層となり、各階層のマージ処理は計算量 $O(n)$。

そのため合計の計算量 $O(nlogn)$ となります。

ただ入力値を保持する領域とは別の一時的なメモリ領域が必要なソートアルゴリズム。

クイックソート.

クイックソートは分割統治法を利用したアルゴリズム。

マージソート同様、再帰的にpatitonを実行。

マージソートとは異なり、追加のメモリ領域は不要なインプレースソートという特徴有り。

計算量 $O(nlogn)$ となり、一般的に最も高速なアルゴリズムと言われます。

再帰処理って何が嬉しいのか、新人の頃はよく理解出来ていませんでしたが、アルゴリズムにおける計算量の観点で考えると、非常に大切な要素だと理解できます。