アルゴリズムの効率性を評価する指標
プログラムの品質を評価する際、コードの可読性や簡潔さだけでなく、「実行効率」が極めて重要な要素となります。アルゴリズムの効率性は、主に以下の2つの観点から測定されます。
- 時間計算量（Time Complexity）： アルゴリズムが実行を完了するまでにかかる時間の目安。
- 空間計算量（Space Complexity）： アルゴリズムが実行中に必要とするメモリ容量の目安。
現代のコンピュータはメモリ容量が飛躍的に増大しているため、多くの場合、空間計算量よりも時間計算量の最適化が優先されます。しかし、組み込みシステムや大規模データ処理では、依然として両方のバランスが重要です。
時間計算量と「大O記法」
アルゴリズムの実行時間は、使用するハードウェアやコンパイラによって変動するため、絶対的な秒数で表すのは不適切です。そのため、入力サイズ N に対して実行回数がどのように増加するかを示す数学的関数を用います。これを一般に大O記法（Big O notation）と呼びます。
計算量の導出ルール
- 定数項はすべて「1」に置き換える。
- 最高次の項のみを残し、それ以外の項を省略する。
- 最高次の項の係数を除去する。
// 時間計算量の例
void example_func(int n) {
int total = 0;
// 2重ループ：N^2 回
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
total++;
}
}
// 単一ループ：2 * N 回
for (int k = 0; k < 2 * n; ++k) {
total++;
}
// 定数回：10回
for (int m = 0; m < 10; ++m) {
total++;
}
}
上記のコードの実行回数は N^2 + 2N + 10 です。大O記法のルールを適用すると、最も影響力の大きい N^2 が残り、時間計算量は O(N^2) となります。
一般的な時間計算量のパターン
1. O(1) 定数時間
入力サイズに関係なく、常に一定のステップ数で終了します。
void constant_time(int n) {
int val = n * 2;
printf("%d", val);
}
2. O(N) 線形時間
入力サイズ N に比例して実行時間が増加します。
int find_max(int* arr, int size) {
int max_val = arr[0];
for (int i = 1; i < size; ++i) {
if (arr[i] > max_val) max_val = arr[i];
}
return max_val;
}
3. O(log N) 対数時間
二分探索のように、ステップごとに探索範囲が半分になるアルゴリズムが該当します。
int binary_search(int* data, int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (data[mid] == target) return mid;
if (data[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
4. O(2^N) 指数時間
再帰を用いたフィボナッチ数列の計算などが代表例で、入力が少し増えるだけで計算量が爆発的に増加します。
long long fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
空間計算量の考え方
空間計算量は、プログラム自体が占有する領域を除き、アルゴリズムが動作するために追加で必要とするメモリ量を指します。
O(1) の例
変数を数個程度しか使わない場合、空間計算量は定数となります。
void swap_elements(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
O(N) の例
入力サイズに応じた動的配列を確保する場合などが該当します。
int* create_sequence(int n) {
int* buffer = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; ++i) buffer[i] = i;
return buffer;
}
実践的な最適化の例
欠落した数値の特定
0からNまでの数値が含まれる配列から1つだけ欠けている数を見つける問題。
- ソートを用いる方法: O(N log N) 時間。
- 合計値の差を利用する方法: 0からNの総和から配列の合計を引く。O(N) 時間、O(1) 空間。
- XOR演算を利用する方法: すべての要素と0〜NをXORする。O(N) 時間、O(1) 空間。
配列の回転（Rotate Array）
サイズNの配列を右にK回シフトさせる問題。
- 一時的な配列を作成: O(N) 時間、O(N) 空間。
- 反転（Reverse）アルゴリズム: 配列全体を反転し、次に分割された各部分を反転させる。O(N) 時間、O(1) 空間。
void reverse(int* arr, int start, int end) {
while (start < end) {
int t = arr[start];
arr[start++] = arr[end];
arr[end--] = t;
}
}
void rotate(int* nums, int n, int k) {
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}