【C言語】第8章第15回：アルゴリズムの計算量と最適化
アルゴリズムの計算量は、その効率性を評価するための指標です。本記事では、時間計算量と空間計算量の基礎を学び、効率的なプログラムを設計する方法について学びます。
0. 記事の概要
この記事を読むメリット
- 計算量の理解：アルゴリズムの効率を定量的に評価する力がつきます。
- プログラムの最適化：計算量を最小化して、実用的で効率的なコードを書くスキルが得られます。
- 実践的なスキル：C言語でのアルゴリズム設計と最適化手法を習得できます。
この記事で学べること
- 時間計算量と空間計算量の基本概念
- 計算量の評価方法と具体例
- アルゴリズム最適化の実践的な手法
1. アルゴリズムの計算量の基礎
1.1 計算量とは？
計算量とは、アルゴリズムの実行に必要なリソース（時間や空間）の量を示す指標です。
1.2 時間計算量と空間計算量
- 時間計算量：アルゴリズムの実行に要する時間を入力サイズの関数として表現します。
- 空間計算量：アルゴリズムが必要とするメモリの量を示します。
1.3 計算量のオーダー
計算量のオーダーは、入力サイズに対する計算量の増加率を示します。主なオーダー：
- O(1)：定数時間
- O(log n)：対数時間
- O(n)：線形時間
- O(n^2)：二次時間
2. アルゴリズムの評価と実装例
2.1 線形探索（O(n)）
#include <stdio.h>
// 線形探索
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // 見つかった位置を返す
}
}
return -1; // 見つからない場合
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int result = linearSearch(arr, size, target);
if (result != -1) {
printf("Found at index %d\n", result);
} else {
printf("Not found\n");
}
return 0;
}
動作解説
- ループを使用：配列を先頭から順に探索します。
- 条件一致：ターゲット値が見つかった場合、そのインデックスを返します。
- 結果出力：ターゲットが見つかったかどうかを表示します。
2.2 バイナリ探索（O(log n)）
#include <stdio.h>
// バイナリ探索
int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 7;
int result = binarySearch(arr, size, target);
if (result != -1) {
printf("Found at index %d\n", result);
} else {
printf("Not found\n");
}
return 0;
}
動作解説
- 初期化：配列の左端と右端を設定します。
- 中央確認：ターゲットと中央値を比較して探索範囲を半分に絞ります。
- 結果出力：ターゲットが見つかったかどうかを表示します。
3. アルゴリズム最適化の実践例
3.1 メモ化を使用した最適化
#include <stdio.h>
#define MAX 100
int memo[MAX];
// フィボナッチ数列（メモ化）
int fib(int n) {
if (n <= 1) {
return n;
}
if (memo[n] != -1) {
return memo[n];
}
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
int main() {
for (int i = 0; i < MAX; i++) {
memo[i] = -1;
}
int n = 10;
printf("Fibonacci(%d): %d\n", n, fib(n));
return 0;
}
動作解説
- メモ初期化：計算済み値を保存する配列を初期化します。
- 再利用：計算済みの値を再利用して計算量を削減します。
4. 練習問題
以下の課題に挑戦して、計算量と最適化の理解を深めましょう。
- 挿入ソート（Insertion Sort）の時間計算量を計算し、最適化してください。
- 部分和問題を解くアルゴリズムの時間計算量を評価してください。
- 再帰的なクイックソートをメモ化で最適化するプログラムを実装してください。
5. 練習問題の解答と解説
問1の解答
#include <stdio.h>
// 挿入ソート
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {9, 7, 5, 3, 1};
int size = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, size);
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
このアルゴリズムの時間計算量はO(n^2)ですが、小規模な入力には効率的です。
6. まとめ
本記事では、アルゴリズムの計算量と最適化について学びました。次回は、さらに高度な最適化手法を学びます。