自分の作成したプログラムが動かない、時間がかかるなどでツールやシステムの使い勝手が左右されることが多々あります。
また、作成している最中に作ったものが動くかどうかわからない不安に駆られることもあると思います。
今回はアルゴリズムの計算量について、まとめてみました。参照いただければ幸いです。
ソートアルゴリズムの計算量
ここでは、ソートアルゴリズムの計算方法についてまとめました。ソートを行うことで、プログラム全体の計算量が減ることがあるので是非押さえておきたい内容です。
バブルソート（Bubble Sort）
バブルソートは、隣り合う要素を比較し、必要に応じて交換することで配列を並び替えます。このアルゴリズムの計算量は、最悪の場合において O(n^2) であり、平均的な場合においても O(n^2) です。
選択ソート（Selection Sort）
選択ソートは、配列の中から最小値を探し、先頭に移動させ、残りの配列に対して同じ操作を繰り返すことで、配列をソートします。このアルゴリズムの計算量は、最悪の場合において O(n^2) であり、平均的な場合においても O(n^2) です。
挿入ソート（Insertion Sort）
挿入ソートは、未ソートの部分の先頭から要素を1つずつ取り出し、それをソート済みの部分に挿入することで配列をソートします。このアルゴリズムの計算量は、最悪の場合において O(n^2) であり、平均的な場合においても O(n^2) です。
マージソート（Merge Sort）
マージソートは、分割統治法を使って配列をソートするアルゴリズムです。配列を2つに分割し、それぞれを再帰的にソートし、最後にマージすることで、全体をソートします。このアルゴリズムの計算量は、最悪の場合においても平均的な場合においても O(n log n) です。
クイックソート（Quick Sort）
クイックソートは、分割統治法を使って配列をソートするアルゴリズムです。配列の中からピボットと呼ばれる要素を選び、それを基準にして配列を2つに分割し、それぞれを再帰的にソートすることで、全体をソートします。このアルゴリズムの計算量は、最悪の場合において O(n^2) であり、平均的な場合においては O(n log n) です。
ソートアルゴリズムの計算量一覧
以下に、ソートアルゴリズムの計算量をまとめた表を示します。
| アルゴリズム | 最悪の場合の計算量 | 平均的な場合の計算量 |
| バブルソート | O(n^2) | O(n^2) |
| 選択ソート | O(n^2) | O(n^2) |
| 挿入ソート | O(n^2) | O(n^2) |
| マージソート | O(n log n) | O(n log n) |
| クイックソート | O(n^2) | O(n log n) |
探索アルゴリズムの計算量
探索アルゴリズムはかなりの頻度で使うものと思います。計算量を把握しておくと何かと便利と思います。
線形探索（Linear Search）
線形探索は、配列の中から目的の要素を探し出すアルゴリズムです。配列を先頭から順に探索し、目的の要素が見つかるまで繰り返します。このアルゴリズムの計算量は、最悪の場合において O(n) であり、平均的な場合においても O(n) です。
二分探索（Binary Search）
二分探索は、ソートされた配列の中から目的の要素を探し出すアルゴリズムです。配列の中央の要素を選び、目的の要素がその中央よりも大きいか小さいかに応じて、探索範囲を半分に狭めていくことで目的の要素を探します。このアルゴリズムの計算量は、最悪の場合において O(log n) であり、平均的な場合においても O(log n) です。
探索アルゴリズムの計算量一覧
以下に、探索アルゴリズムの計算量をまとめた表を示します。
| アルゴリズム | 最悪の場合の計算量 | 平均的な場合の計算量 |
| 線形探索 | O(n) | O(n) |
| 二分探索 | O(log n) | O(log n) |
データ構造による計算量
データ構造にストック・探索・取り出しを行うことで計算量を削減することができます。こちらについてもまとめてみました。
配列
配列は、同じ型の要素が一列に並んだデータ構造です。各要素は一意のインデックスで識別され、O(1)の時間でアクセスすることができます。ただし、要素を挿入や削除する場合は、挿入や削除位置以降の要素を一つずつずらす必要があるため、O(n)の時間がかかります。
配列は、インデックスを使って要素にアクセスする必要がある場合に最適です。また、要素数が固定である場合や、要素数が小さく動的な変更が必要ない場合にも有効です。
連結リスト
連結リストは、要素がノードと呼ばれるオブジェクトで表され、各ノードが次のノードへの参照を持っているデータ構造です。最初のノードを先頭とし、最後のノードを末尾とします。
連結リストは、アクセスにはO(n)の時間がかかりますが、ノードを先頭や末尾に挿入や削除する場合はO(1)の時間で行うことができます。また、空間効率に優れており、要素数が大きく動的な変更が頻繁に必要な場合に有効です。
スタック
スタックは、最後に追加された要素が最初に取り出される後入れ先出し（LIFO）のデータ構造です。スタックに要素を追加する操作をpush、スタックから要素を取り出す操作をpopと呼びます。
スタックは、アクセスや削除にO(1)の時間がかかりますが、挿入にはO(1)の時間ではありません。また、先頭以外の要素にアクセスすることはできません。スタックは、一時的なデータを保存する場合や、再帰的な処理を行う場合に有効です。
キュー
キューは、最初に追加された要素が最初に取り出される先入れ先出し（FIFO）のデータ構造です。キューに要素を追加する操作をenqueue、キューから要素を取り出す操作をdequeueと呼びます。
キューは、アクセスや削除にO(1)の時間がかかりますが、挿入にはO(1)の時間ではありません。また、先頭以外の要素にアクセスすることはできません。キューは、待ち行列を表現する場合や、幅優先探索を行う場合に有効です。
木構造
木構造は、一つの要素（ルートノード）から始まり、複数の子ノードを持つノードが繋がり、グラフ構造を形成するデータ構造です。木構造は、探索や挿入にO(log n)の時間がかかりますが、木の形状によってはO(n)の時間がかかる場合もあります。
二分木は、各ノードが最大で2つの子ノードを持つ木構造です。二分木は、探索や挿入にO(log n)の時間がかかります。平衡二分木は、各ノードの左右の部分木の高さが最大で1しか異ならないように保たれた二分木です。平衡二分木は、探索や挿入にO(log n)の時間がかかるので、データ検索などに使われます。
ハッシュテーブル
ハッシュテーブルは、キーと値のペアを格納するデータ構造で、キーをハッシュ関数によって計算し、特定のバケットに格納します。キーに対応する値を取得する場合は、ハッシュ関数によって計算されたバケットに格納されている値をO(1)の時間で取得できます。
ハッシュテーブルは、キーをハッシュ関数で計算するため、最悪の場合にはアクセスや挿入にO(n)の時間がかかる場合があります。また、衝突が起こる場合には、別のバケットに値を挿入するための追加的な処理が必要になる場合があります。
グラフ構造
グラフ構造は、ノードとエッジから構成されるデータ構造で、複数のノードがエッジで繋がれています。グラフ構造は、探索や最短経路探索などに使われます。
深さ優先探索（DFS）は、あるノードから始まり、その子ノードを再帰的に探索する探索アルゴリズムです。DFSの実行時間は、グラフの全てのノードとエッジを訪問するため、O(|V|+|E|)の時間がかかります。
幅優先探索（BFS）は、あるノードから始まり、そのノードと隣接するノードを順番に探索する探索アルゴリズムです。BFSの実行時間は、すべてのノードとエッジを一度だけ訪問するため、O(|V|+|E|)の時間がかかります。BFSは、最短経路探索などに使われます。
データ構造の計算量一覧
データ構造によってアルゴリズムの計算量は大きく変わります。以下に、代表的なデータ構造とその計算量をまとめた表を示します。
| データ構造 | アクセス | 挿入 | 削除 | 探索 |
| 配列 | O(1) | O(n) | O(n) | O(n) |
| 連結リスト | O(n) | O(1) | O(1) | O(n) |
| スタック | O(1) | O(1) | O(1) | ー |
| キュー | O(1) | O(1) | O(1) | ー |
| ハッシュテーブル | O(1) | O(1) | O(1) | O(1) |
| 二分木 | O(log n) | O(log n) | O(log n) | O(log n) |
上記の表では、アクセスは指定したインデックスの要素にアクセスする操作を、挿入は要素を追加する操作を、削除は要素を削除する操作を、探索は指定した要素がデータ構造に含まれているかを調べる操作を表しています。ただし、スタックやキューについては、削除は先入れ先出し（pop）または後入れ先出し（dequeue）という操作を指しています。
まとめ
プログラムの計算量とデータ構造に関する内容をまとめました。アルゴリズムやデータ構造の選択は、プログラムの実行時間やメモリ使用量に大きな影響を与えるため、理解しておくことが重要です。
