ビッグオー記法

Daily Blogging71日目

ビッグオー記法って実務で意識したことがほとんどないなぁ

ビッグオー記法とは

英語で言うと、Big-O notation
アルゴリズムにおいて、「計算量やメモリ消費量がデータ量に応じてどれくらい増加するのか」を示すもの
それぞれのアルゴリズムの、一番時間がかかるパターンの結果を示すよ

ビッグオー記法の種類

結構色々ある

記法	増加のイメージ	例
O(1)	一定（データ量に関係なく高速）	配列のインデックスアクセス arr[i]、ハッシュの検索 hash[key]
O(log N)	ゆっくり増加、データ量が増えても計算量が急増しない	二分探索とか
O(N)	データ量の数だけ増加	ループ処理 (each や map)、線形探索※1 (arr.include?(x))
O(N log N)	準線形	クイックソート、マージソート
O(N²)	急激に遅くなる（Nが大きいと危険）	二重ループ (each のネスト) 、バブルソート
O(2^N)	爆発的に増加（Nが少し増えるだけで遅い）	再帰的な組み合わせ探索（フィボナッチの再帰計算）
O(N!)	最悪（ほぼ実行不可能）	全順列の探索（巡回セールスマン問題）

※1 端から順にデータを探すやつ

増加する処理のイメージ

ビッグオー記法	10個のデータ (N=10)	100個のデータ (N=100)	1,000個のデータ (N=1,000)	1,000,000個のデータ (N=1,000,000)
O(1)	1回	1回	1回	1回
O(log N)	約3回	約7回	約10回	約20回
O(N)	10回	100回	1,000回	1,000,000回
O(N log N)	約30回	約700回	約10,000回	約20,000,000回
O(N²)	100回	10,000回	1,000,000回	1兆回
O(2^N)	1,024回	約10³⁰回	≈10³⁰回	計算不可
O(N!)	3,628,800回	計算不可	計算不可	計算不可

Rubyの例

Rubyでビッグオー記法を意識してみよう

O(1)

どれだけデータ量が増えても、直接指定しちゃえば計算量は変わらないよね

# 配列の要素に直接アクセス（O(1)）
arr = [1, 2, 3, 4, 5]
puts arr[2] # → 3 （高速）

# ハッシュでの値取得（O(1)）
hash = { a: 1, b: 2, c: 3 }
puts hash[:b] # → 2 （高速）

# Setを使った高速検索（O(1)）
require 'set'
set = Set.new([1, 2, 3, 4, 5])
# Setは内部的にはHashの形になり、hash[:b]と同じ検索になる
# Arrayのinclude?は線形探索
puts set.include?(3) # → true

O(log N)

Rubyというか、DBアクセスしてデータを取得する場合、インデックスを利用できるようにしておけばB-tree方式で二分探索になって高速化できる。

あとは、Arrayのbsearchも使える。
※ソート済みの配列の場合

arr = [1, 3, 5, 7, 9, 11, 13, 15]

result = arr.bsearch { |x| x >= 7 }
puts result  # 出力: 7

arr = [1, 3, 5, 7, 9, 11, 13, 15]

# 最初に条件を満たすインデックスを取得
index = arr.bsearch_index { |x| x >= 7 }
puts index  # 出力: 3

O(N)

# Railsの N+1問題（O(N²) になりやすい）
users = User.all
users.each do |user|
  puts user.posts.count
end

# `includes` を使って O(N) に最適化
users = User.includes(:posts)
users.each do |user|
  puts user.posts.count # 事前にロードするため高速
end

O(N²)

Arrayのcombinationが使える

# O(N²) のネストされたループ（遅い）
arr = [1, 2, 3, 4, 5]
arr.each do |x|
  arr.each do |y|
    puts "#{x}, #{y}"
  end
end

# combinationが２つの値の全組み合わせを作ってくれる
arr.combination(2).each do |x, y|
  puts "#{x}, #{y}"
end