【Go言語でソートアルゴリズムを学ぶ】計算量について
📅 October 13, 2021
•⏱️ 1 min read
ソートアルゴリズムをGo言語で実装してみることでその仕組みと計算量について理解します。 複数の投稿に分けていきます。 今回は、各アルゴリズムの計算量を比較します。
ソートアルゴリズム
取り上げるソートアルゴリズム
- バブルソート
- クイックソート
- マージソート
- ヒープソート
計算量オーダー
計算量オーダーとはアルゴリズムへの入力サイズをnとして、アルゴリズムの計算実行時間がnに応じてどう変化するかを表したものです。
| アルゴリズム | 平均計算量 | 最悪計算量 | 安定性 |
|---|---|---|---|
| バブルソート | O(n^2) | O(n^2) | あり |
| クイックソート | O(nlogn) | O(n^2) | なし |
| マージソート | O(nlogn) | O(nlogn) | あり |
| ヒープソート | O(nlogn) | O(nlogn) | なし |