Rubyで学ぶビッグオー（Big-O）記法：アルゴリズムの効率を直感的に理解する

かつて「それのビッグオー記法は何ですか？」という質問を聞くことほど怖いものはありませんでした。学校で習った記憶はあるものの、数学（決して得意科目ではありませんでした）に関わる話題だったため、記憶から完全に消し去っていたのです。

しかし、キャリアが進むにつれて、私は次のような場面に直面するようになりました。

• パフォーマンスチャートを眺める
• 遅いクエリのデバッグに苦戦する
• 「負荷が増えたときにコードは耐えられるのか検討しましたか？」と問われる

そろそろ原点回帰して（分かりますかね？）ビッグオーを学び直そうと決めたとき、その驚くほどシンプルな本質に気づきました。この記事では学んだことを共有します。エンジニアの皆さんが面接で見事に合格できるだけでなく、高性能でスケーラブルなシステムを構築できるようになることを願っています。

安心してください。ビッグオーは見た目ほど怖くありません。一度理解してしまえば、プロファイリングツールを実行しなくても、アルゴリズムを見ただけでその効率を簡単に見極められるようになります。

ビッグオー記法とは？

ビッグオー記法とは、「このアルゴリズムの最悪ケースのパフォーマンスはどうなっている？」と表現するための洗練された方法です。関数がO(n)やO(1)と表記されているのを見たことがあるかもしれません。それぞれ次のような意味です。

• O(n) — 入力サイズ（n）が増えるにつれて、最悪実行時間が線形に増加する
• O(1) — 入力サイズにかかわらず、最悪実行時間が一定である

そして、これを本当に理解するには、漸近線について学ぶ必要があります。

漸近線とは？

高校の代数の授業を思い出して、教科書のほこりを払い、極限と漸近線の章を開いてみましょう。

• 極限分析： 関数がある値に近づくとき、何が起こるかを調べる
• 漸近解析： f(x)が無限大に近づくとき、何が起こるかを調べる

例として、関数f(x) = x² + 4xをグラフに描いてみましょう。

次のような分析が可能です。

• 極限分析： xが増加するとf(x)は無限大に近づきます。つまり、xが無限大に近づくときのf(x) = x² + 4xの極限は無限大であると言えます。
• 漸近解析： xが非常に大きくなると、4xの項はx²の項と比べて無視できるほど小さくなります。つまり、無限大に近づくxに対して、f(x) = x² + 4xはほぼf(x) = x²と等価になると言えます。

関数の一部が「無視できる」と言える理由を理解するために、元の関数にさまざまな数値を代入してみましょう。例えば、x = 1のとき、関数は1 + 4（= 5）を返します。一方、x = 2,000のとき、関数は4,000,000 + 8,000（= 4,008,000）を返します。x²の項が合計に占める割合は、4xよりもはるかに大きいのです。

ビッグオー記法とは、入力サイズの変化に伴ってアルゴリズムの実行時間がどう変化するかを記述する一つの方法なのです。

アルゴリズムの実行時間を決めるものは？

干し草の山から針を見つけるのにどれくらいかかるかと聞かれたら、山の中に干し草がどれだけあるか知りたいと思うでしょう。「10本」と答えられれば、1〜2分で見つけられると自信を持てますが、「1,000本」と言われたら、あまり乗り気にはならないはずです。

もう一つ知っておきたい情報があります。干し草が1本増えるごとに探索時間はどれだけ伸びるのか？そして、干し草の量が無限に近づくと何が起こるのか？ということです。

これは先ほどの漸近解析の例と非常によく似ています。理解を確実にするためにもう一つ例を見てみましょう。関数f(x) = 5x² + 100x + 50を考えます。この関数の2つの部分を別々にプロットできます。

前の例と同様に、5x²の項は最終的に100x + 50の項より大きくなるため、後者を切り捨てて、「f(x) = 5x² + 100x + 50の実行時間はx²のように増加する」と言えます。

もちろん、実際にプログラムを実行するコンピュータの処理速度や使用するプログラミング言語など、実行時間に影響を与える他の要因も存在することは付記しておく価値があります。

線形探索のビッグオーを求める

線形探索アルゴリズムのビッグオー分析をしてみましょう。線形探索はデータセットの先頭からスタートし、目的の要素が見つかるまで順番にたどっていく手法です。

Rubyでの実装は以下のとおりです。

def find_number_via_linear_search(array, target)
  counter = 0 

  # インデックス0から配列の末尾まで順に走査する
  while counter < array.length 
    if array[counter] == target 
      # 目的の要素が見つかったら終了
      return "linear search took: #{counter} iterations" 
    else 
      counter += 1 
    end 
  end 

  return "#{target} not found" 
end 

このメソッドは次のように使えます。

# 50個の整数を持つ配列を作成し、
# 順序をシャッフルして面白くする
array = [*1..50].shuffle 

find_number_via_linear_search(array, 24)

何度か実行したところ、次の結果が得られました。

=> "linear search took: 10 iterations"
=> "linear search took: 11 iterations"
=> "linear search took: 26 iterations"

関数のビッグオー記法を分析するとき、私たちが注目するのは最悪ケース（上限漸近境界とも呼ばれます）です。

直感的に考えると、反復回数の最小値は1です。これは目的の要素が配列のインデックス0の位置にある場合に発生します。最大の反復回数（最悪ケース）は50です。これは目的の要素が配列内に存在しなかった場合に起こります。

配列に100個の要素があれば、最悪ケースは100回の反復になります。200個なら200回です。したがって、線形探索のビッグオー記法は単純にO(n)となります。ここでnは要素の数です。

もう少し複雑な例：二分探索！

次に二分探索を考えてみましょう。事前にソート済みの配列に対する二分探索は、次の手順で行います。

1. 中央の要素を取り出す
   2. element == targetなら完了
   3. element > targetなら配列の上半分を破棄
   4. element < targetなら配列の下半分を破棄
   5. 残りの配列でステップ1からやり直す

補足：Rubyistの方なら、このアルゴリズムを実装してくれる組み込みのbsearchメソッドがあることをご存じでしょう！

例えば、辞書で「pineapple」という言葉を探しているとしましょう。まず辞書の中央のページを開きます。そこに偶然「pineapple」があれば完成です！

しかし、おそらく辞書の中央はまだ「p」のセクションには達していないので、「llama」という言葉が見つかるかもしれません。「L」は「P」より前に来るので、辞書の下半分全体を破棄します。次に、残った部分で同じプロセスを繰り返します。

線形探索と同様に、二分探索の最良ケースの実行時間は1回の反復です。では、最悪ケースはどうでしょうか？16個の要素を持つ配列の例があります。二分探索を使って23という数字を見つけたいとしましょう。

[2, 3, 15, 18, 22, 23, 24, 50, 65, 66, 88, 90, 92, 95, 100, 200]

最初のステップは、インデックス7にある数字50を確認することです。50は23より大きいため、右側をすべて破棄します。配列は次のようになります。

[2, 3, 15, 18, 22, 23, 24, 50]

中央の要素は今や18で、23より小さいので、今回は下半分を破棄します。

[22, 23, 24, 50]

さらに絞り込むと

[22, 23]

最終的に

[23]

合計で、長さ16の配列から目的の数字を見つけるために、配列を半分に分割する操作を4回行う必要がありました。

一般化すると、二分探索の最悪ケースは、配列を半分に分割できる最大回数に等しいと言えます。

数学では、「ある数を何回掛ければ別の数になるか？」という問いに答えるために対数を使います。対数をこの問題に適用すると、次のようになります。

したがって、二分探索のビッグオー、つまり最悪実行時間はO(log₂ n)（底2の対数）であると言えます。

まとめ

ビッグオー記法とは、「ねえ、これの最悪ケースはどうなってる？」と尋ねるための洗練された方法です。コンピュータサイエンスを離れて、現実世界の例を挙げましょう。壊れた蛇口の修理費用を配管工に尋ねるとき、彼はこう答えるかもしれません。「ええと、2,000ドルを超えることはないと保証しますよ。」これは上限ではありますが、あまり役に立つ情報ではありません。

このため、他のビッグオー記法もよく活用されます。例えば、ビッグシータ（Θ）は下限と上限の両方を考慮します。この場合、配管工は「1,000ドル未満にはなりませんが、2,000ドルを超えることもありません」と答えるでしょう。こちらの方がはるかに有用ですね。

お読みいただきありがとうございました。この記事が、ビッグオー記法を少なくとも少しでも身近に感じるきっかけになれば幸いです！