1. 計算量オーダーとは
アルゴリズムの効率を評価する指標であり、入力サイズ n に対して処理時間やメモリ使用量がどのように増加するかを表します。一般的な表記として、O(1)、O(n)、O(n^2)、O(log n) などがあります。
2. ランダウの記号（O 記法）
計算量オーダーを表す際に用いられる記法で、主に以下の特徴があります：
- 最高次数の項のみを考慮：例えば、
7n^2 + 2n + 10という式では、最高次数の項であるn^2のみを考え、他の項は無視します。これは、入力サイズが大きくなるにつれて最高次数以外の項が無視できるほど小さくなるためです。 - 定数倍を無視：
3n^2もn^2も同じO(n^2)として扱います。定数係数はかぎりなく小さくなるため、計算量のオーダー評価では無視されます。
これにより、アルゴリズムの漸近的な振る舞いを簡潔に表現できます。
3. 計算量オーダーの具体例
O(1) : 定数時間
入力サイズに関わらず一定の時間で処理が完了する。
- 例: 配列の特定要素へのアクセス（
array[i]）。 - 理由: インデックスを指定することで、直接メモリアドレスにアクセスできるため、処理時間は一定です。
- C++実装例:
int getElement(int arr[], int index) {
return arr[index];
}O(log n) : 対数時間
入力サイズが増加しても、処理時間の増加が対数的である。
- 例: 二分探索（Binary Search）、平衡二分探索木（AVL 木、赤黒木）の挿入・削除。
- 理由: データを半分に分割しながら処理を進めるため、計算回数は
log nに比例します。 - C++実装例:
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}O(n) : 線形時間
入力サイズに比例して処理時間が増加する。
- 例: 線形探索（リスト内の要素を順に調べる）、配列の全要素の和を求める処理。
- 理由: 各要素を 1 回ずつ処理するため、要素数 \(n\) に応じて処理時間が増加します。
- C++実装例:
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) return i;
}
return -1;
}O(n \log n) : 準線形時間
線形時間に対数的な要素が加わる。
- 例: 高速なソートアルゴリズム（マージソート、クイックソート）、ヒープソート。
- 理由: ソート処理のたびにリストを分割し、それぞれの部分をソートするため、処理時間は
O(n)に対数的なO(\log n)の要素が加わります。 - C++実装例:
void mergeSort(int arr[], int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// マージ処理は省略
}O(n^2) : 二乗時間
入力サイズの二乗に比例して処理時間が増加する。
- 例: バブルソート、挿入ソート、選択ソート（ネストされた二重ループ）。
- 理由: 各要素に対して全要素を比較するため、処理回数が
n \times n = n^2となります。 - C++実装例:
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}4. 計算量オーダーの活用方法
アルゴリズムを設計・選択する際には、以下の点を考慮します：
- 問題の規模（入力サイズ
n）: 問題の規模に応じて、許容される計算量オーダーが変わります。 - 実行時間の制約: 例えば、1 秒以内に処理を完了させたい場合、
nの大きさに応じて適切な計算量オーダーを選択する必要があります。
一般的な目安として、n が大きくなるほど、低い計算量オーダー（例：O(n) や O(n \log n)）のアルゴリズムが求められます。
5. まとめ
計算量オーダーは、アルゴリズムの効率を評価・比較するための重要な指標です。アルゴリズムの設計や選択時には、入力サイズや実行時間の制約を考慮し、適切な計算量オーダーのアルゴリズムを選ぶことが重要です。
参考文献
1. アルゴリズムとデータ構造（著：渡部有隆）
2. プログラミングコンテストチャレンジブック（著：秋葉拓哉）
