Big O記法（ビッグオー）を理解できていなかったため、備忘録としてまとめます。
- ぼくは独学で未経験から従業員300名以上の自社開発企業へ転職しました。
- 実務ではVue.jsとRailsを毎日書いています。
- 初心者や駆け出しエンジニアがつまづくポイントも身をもってよく理解しています。
問題
アルゴリズムの勉強をしようと思い技術書を読み始めたんですが、最初に出てきた「Big O記法」が全然理解できませんでした、、。
解決策
解決策というか、調べて内容を理解できたので、まとめます。
Big O記法はアルゴリズムの効率を示す表記方法です。
入力値のサイズが増えるにつれてアルゴリズムの実行時間やメモリの使用量がどう変化するか？を表します。
Big O記法は最悪のケースを想定したパフォーマンスを示しているため、実際の計算量と完全に一致するわけではありませんが、計算量を大まかに予想する上ではとても有効な指標です。
ここからは代表的なBig O記法の例を紹介していきます。
定数時間：O(1)
「O(1)」という表記は「定数時間」を意味します。
「定数時間」とは、アルゴリズムの実行時間が入力値のサイズを問わず常に一定である場合を指します。
定数時間の例
配列のインデックスを使用して任意の要素にアクセスする操作は、定数時間で実行されるアルゴリズムの一般的な例です。
配列の要素数がいくつであっても、指定したインデックスの要素にアクセスする時間はおなじです。
def access_element(array, index)
return array[index]
end
# 配列の作成
my_array = [1, 2, 3, 4, 5]
# 特定の要素にアクセス
element = access_element(my_array, 2)
puts element # 出力: 3↑の例だと、たとえmy_arrayの要素数が2倍になっても、指定したインデックスへアクセスするための計算量は変わりません。
対数時間：O(log n)
「O(log n)」という表記は「対数時間」を意味します。
「対数時間」とは、入力値のサイズが増加しても、アルゴリズムの実行時間が比較的遅く増加する場合を指します。
対数時間の例
二分探索は対数時間のアルゴリズムの典型的な例です。
def binary_search(array, target)
low = 0
high = array.length - 1
while low <= high
mid = (low + high) / 2
guess = array[mid]
if guess == target
return mid # 目的の値のインデックスを返す
elsif guess > target
high = mid - 1
else
low = mid + 1
end
end
return nil # 目的の値が配列内にない場合
end
# ソート済みの配列
my_array = [1, 3, 5, 7, 9]
# 二分探索を使用して配列内の値を探す
puts binary_search(my_array, 3) # 出力: 1
puts binary_search(my_array, -1) # 出力: nil二分探索の場合、ループ1回毎に探索範囲を半分に絞ります。
そのため入力値のサイズが倍になったとしても、それに比例して処理時間も倍になるわけではありません。
範囲を絞り込む処理が1回増える分だけ、すこし遅くなります。
そのため、二分探索は対数時間のアルゴリズムの典型だと言えます。
線形時間：O(n)
「O(n)」という表記は「線形時間」を意味します。
「線形時間」とは、入力値のサイズに比例してアルゴリズムの実行時間も増加する場合を指します。
入力値のサイズが2倍になると実行時間も約2倍になると予想されるケースです。
線形時間の例
線形探索は線形時間のアルゴリズムの代表です。
線形探索とは、配列の各要素を最初から最後まで順番に調べて、特定の値を見つける探索方法です。
def linear_search(array, target)
array.each_with_index do |item, index|
return index if item == target
end
return nil # 見つからなかった場合
end
# 配列の例
my_array = [4, 2, 5, 1, 3, 9, 8, 6, 7]
# 線形探索を使用して配列内の値を探す
puts linear_search(my_array, 5) # 出力: 2
puts linear_search(my_array, 10) # 出力: nil配列の要素数が増えれば増えるほど、その数だけ要素を調べる回数も増加するため、線形時間のアルゴリズムの典型だと言えますね。
線形対数時間：O(n log n)
「O(n log n)」という表記は「線形対数時間」を意味します。
「線形対数時間」は、線形時間と対数時間が合わさったものです。
線形対数時間の例
線形対数時間の代表例は、マージソートです。
マージソートは、配列の各要素を一度分解し、順序を並び替えてソートした状態で配列に戻すアルゴリズムです。
def merge_sort(array)
return array if array.length <= 1
mid = array.length / 2
left = merge_sort(array[0...mid])
right = merge_sort(array[mid..-1])
merge(left, right)
end
def merge(left, right)
sorted = []
until left.empty? || right.empty?
if left.first <= right.first
sorted << left.shift
else
sorted << right.shift
end
end
sorted + left + right
end
# 配列の例
my_array = [4, 2, 5, 1, 3, 9, 8, 6, 7]
# マージソートを使用して配列をソート
sorted_array = merge_sort(my_array)
puts sorted_array.inspect # 出力: [1, 2, 3, 4, 5, 6, 7, 8, 9]↑のmerge_sortメソッドでは、array.lengthの数が2倍になるとループが1回増えるため、この部分は対数時間（O(log n)）のアルゴリズムです。
一方でmergeメソッドでは要素の数だけ比較をくりかえすため、この部分は線形時間（O(n)）のアルゴリズムです。
なのでマージソート全体で見ると、線形対数時間（O(n log n)）のアルゴリズムとなります。
二乗時間：O(n^2)
「O(n^2)」という表記は「二乗時間」を意味します。
「二乗時間」とは、アルゴリズムの実行時間の増え方が、入力値のサイズの二乗となる場合を指します。
二乗時間の例
二乗時間のアルゴリズムの代表例は、バブルソートです。
バブルソートは、隣同士の要素を順番に比較していってソートするアルゴリズムです。
def bubble_sort(array)
loop do
swapped = false
(array.length - 1).times do |i|
if array[i] > array[i+1]
array[i], array[i+1] = array[i+1], array[i]
swapped = true
end
end
break unless swapped
end
array
end
# 配列の例
my_array = [4, 2, 5, 1, 3, 9, 8, 6, 7]
# バブルソートを使用して配列をソート
sorted_array = bubble_sort(my_array)
puts sorted_array.inspect # 出力: [1, 2, 3, 4, 5, 6, 7, 8, 9]バブルソートの場合、配列の各要素に対して、他のすべての要素と比較する必要はあるため、入力サイズが2倍になると実行時間は4倍、つまり2の二乗になります。
そのためバブルソートは大量のデータを扱うには不向きなアルゴリズムです。
おわりに
Big O記法と代表的な表記の具体例をまとめました。
Railsのようなフレームワークを用いた開発をしていると、日常的にアルゴリズムを意識する場面は少ないです。
しかし、大規模アプリケーションにおけるパフォーマンスのボトルネックを特定したり、スケーラビリティやメンテナンス性を考える上では必須の知識です。
今後もコツコツとこの分野の学習を進めていきます。
コメント