アルゴリズムの効率性
アルゴリズムの効率性は、以下の2つの観点で評価されます。
- 時間計算量: アルゴリズムが動作を完了するまでにかかる時間
- 空間計算量: アルゴリズムが使用するメモリの量
効率的なアルゴリズムは、入力データが増加しても、計算時間やメモリ使用量の増加を抑えられます。
計算量の指標 (Big-O 記法)
計算量は、Big-O記法で表現されます。Big-Oは、入力データサイズ (n) に対するアルゴリズムの動作速度やメモリ使用量の増加を示します。
| 計算量 | 説明 | 例 |
|---|---|---|
| $O(1)$ | 定数時間: 入力サイズに依存せず一定時間で終了 | 配列の要素アクセス |
| $O(log\ n)$ | 対数時間: 入力サイズが倍になっても増加がわずか | 二分探索 |
| $O(n)$ | 線形時間: 入力サイズに比例して時間が増加 | 配列の線形検索 |
| $O(n\ log\ n)$ | 線形対数時間: 比較的効率的 | クイックソート |
| $O(n^2)$ | 二次時間: 入力サイズの2乗に比例して増加 | バブルソート（二重ループ） |
| $O(2^n)$ | 指数時間: 非常に非効率的 | フィボナッチ数列 (再帰) |
線形探索 (Linear Search): O(n)
配列の中から特定の要素を探す単純な方法です。
配列の全要素を1つずつ確認するため、入力サイズ (n) に比例して処理時間が増加します。
package main
func linearSearch(arr []int, target int) bool {
for _, v := range arr {
if v == target {
return true
}
}
return false
}
0~99999の中から、50000を探すベンチマーク
goos: darwin
goarch: amd64
pkg: go-cs
cpu: Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz
BenchmarkLinearSearch-4 412674 2794 ns/op 1 B/op 0 allocs/op
PASS
ok go-cs 1.712s
二分探索 (Binary Search): O(log n)
ソート済み配列を対象に、効率的に特定の要素を探します。
各ステップで検索範囲を半分にするため、計算量は対数的に減少します。
package main
func binarySearch(arr []int, target int) bool {
low, high := 0, len(arr)-1
for low <= high {
mid := (low + high) / 2
if arr[mid] == target {
return true
} else if arr[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return false
}
0~99999の中から、50000を探すベンチマーク
goos: darwin
goarch: amd64
pkg: go-cs
cpu: Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz
BenchmarkBinarySearch-4 58865257 22.09 ns/op 0 B/op 0 allocs/op
PASS
ok go-cs 1.769s
クイックソート（Quick Sort）: O(n log n)
クイックソートは分割統治法を利用した効率的なアルゴリズム。
平均計算量が $O(n\ log\ n)$ です。
package main
func quickSort(arr []int) []int {
// 基本ケース: 要素が1つ以下ならそのまま返す
if len(arr) <= 1 {
return arr
}
// ピボットの選択 (配列の最初の要素)
pivot := arr[0]
// ピボットより小さい要素と大きい要素に分割
var less, greater []int
for _, v := range arr[1:] {
if v <= pivot {
less = append(less, v)
} else {
greater = append(greater, v)
}
}
// 再帰的にソートして結合
return append(append(quickSort(less), pivot), quickSort(greater)...)
}
0~99999をランダムに並べた配列をソートしたベンチマーク
goos: darwin
goarch: amd64
pkg: go-cs
cpu: Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz
BenchmarkQuickSort-4 25 47294301 ns/op 70300818 B/op 384861 allocs/op
PASS
ok go-cs 2.648s
バブルソート (Bubble Sort): O(n^2)
2つの隣接する要素を比較して並び替えるアルゴリズム。
内側のループが外側のループに対して繰り返されるため、計算量が $O(n^2)$ になります。
package main
func bubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n; i++ {
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
return arr
}
0~99999をランダムに並べた配列をソートしたベンチマーク
goos: darwin
goarch: amd64
pkg: go-cs
cpu: Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz
BenchmarkBubbleSort-4 1 14169351466 ns/op 802824 B/op 2 allocs/op
PASS
ok go-cs 14.664s