Ruby開発者のための時間計算量とBig O記法 徹底解説ガイド

時間計算量は、コンピュータサイエンスの中でも最も興味深い概念のひとつです。しかも、特別な学位がなくても十分に理解できます。

この概念が面白いのは、あるアルゴリズムやプログラムがなぜ遅いのかを見抜き、どうすれば高速化できるのかを明確にしてくれる点にあります。

もちろん、自分が書いたコードにもすぐに応用できます。

さらに、教科書に載っているような高度なアルゴリズムだけではなく、日常的に書くコードにも役立つのがポイントです。本記事の後半で実際に確認していきます。

まずは、「遅い」と「速い」の定義から整理しましょう。

「遅い」と「速い」の定義

100万個の数字を150ミリ秒(ms)でソートするのは、果たして速いのでしょうか?

個人的にはかなり速いと感じます。しかし、これは時間計算量が答えようとしている問いではありません。

時間計算量で知りたいのは、入力サイズが大きくなるにつれて、アルゴリズムの性能がどう変化するかという点です。

ここでいう「入力サイズ」とは、関数やメソッドに渡される引数のことです。たとえばメソッドが1つの文字列を受け取るなら、その文字列が入力となり、文字列の長さが入力サイズにあたります。

Big O記法とは

Big O記法を使うと、アルゴリズムを性能の観点から分類できます。

記法は次のように表します。

O(1)

この O(1) は「定数時間(constant time)」のアルゴリズムを表しています。

つまり、処理すべき作業量がどれだけ増えても、完了までにかかる時間は常に同じであるという意味です。

もうひとつは「線形時間(linear time)」です。

O(n)

「n」は入力のサイズ(文字列の長さ、配列の要素数など)を表します。これは、処理時間が入力サイズに対して1:1の割合で増加することを意味します。入力サイズを2倍にすれば、処理時間も2倍になるのです。

主要な計算量を一覧表にまとめました:

記法	名称	説明
O(1)	定数時間	常に同じ時間で完了する。
O(log n)	対数時間	ループ1回ごとに処理量が半分になる(二分探索など)。
O(n)	線形時間	処理時間が入力サイズに比例して増加する。
O(n log n)	線形対数時間	ネストしたループで、内側のループが log n 時間で動くケース。クイックソート、マージソート、ヒープソートなどが該当。
O(n^2)	二次時間	処理時間が 入力サイズ ^ 2 に比例して増加する。全要素を走査するループの中で、さらに全要素を走査するループがある場合(ネストしたループ)に見られる。
O(n^3)	三次時間	n^2 と同様だが、処理時間が n^3 の割合で増加する。三重にネストしたループが目印。
O(2^n)	指数時間	処理時間が 2 ^ 入力サイズ の割合で増加する。n^2 よりはるかに遅いため混同しないこと!再帰版フィボナッチ算法などが例。

アルゴリズム分析の考え方

入力を「n」個の要素を持つ配列としてイメージすると、直感的な感覚を養えます。

たとえば、偶数である要素をすべて見つけたいとしましょう。これを実現する唯一の方法は、すべての要素を一度読み込み、条件に合致するか確認することです。

[1,2,3,4,5,6,7,8,9,10].select(&:even?)

一部の数字を読み飛ばすと、探している数を見逃す可能性があります。そのため、これは線形時間のアルゴリズム、つまり O(n) になります。

同じ問題への3つの異なる解法

個別の例を分析するのも面白いですが、この概念を本当に理解するには、同じ問題を異なる方法で解いてみるのが効果的です。

ここでは、スクラブル(Scrabble)の解答チェックを題材に、3つのコード例を見ていきます。

スクラブルとは、文字のリスト(ollhe など)が与えられ、それらの文字だけで単語(hello など)を作れるかを判定するゲームです。

最初の解法がこちら:

def scramble(characters, word)
  word.each_char.all? { |c| characters.count(c) >= word.count(c) }
end

このコードの時間計算量がわかりますか?鍵は count メソッドにあるので、まずこのメソッドの動作を理解してください。

答えは O(n^2) です。

理由はこうです。each_char によって文字列 word の全文字を走査します。これだけなら線形時間 O(n) ですが、ブロックの中に count メソッドがあります。

count メソッドは実質的にもうひとつのループであり、文字列全体を再度走査して文字を数えています。

2番目の解法

さて、どうすればもっと効率化できるでしょうか?ループの回数を減らす方法はないでしょうか?

文字を数える代わりに削除してしまえば、走査対象の文字が減ります。

2番目の解法がこちら:

def scramble(characters, word)
  characters = characters.dup
  word.each_char.all? { |c| characters.sub!(c, "") }
end

こちらは少し興味深い実装です。探している文字が文字列の先頭近くにあるという最良のケースでは、count 版より大幅に高速になります。

しかし、文字がすべて末尾にあり、word 内の出現順と逆の順序で並んでいるような最悪のケースでは、count 版とほぼ同等の性能になります。つまり、依然として O(n^2) のアルゴリズムだと言えます。

なお、word 内の文字がまったく利用できないケースを心配する必要はありません。all? メソッドは sub! が false を返した時点で即座に評価を打ち切るためです。ただし、この挙動を知るには、一般的なRuby講座の範囲を超えた深い学習が必要になります。

ハッシュを使った3番目の解法

ブロック内のループを一切なくせたらどうでしょう?それはハッシュを使えば実現できます。

def scramble(characters, word)
  available = Hash.new(1)

  characters.each_char { |c| available[c] += 1 }
  word.each_char.all? { |c| available[c] -= 1; available[c] > 0 }
end

ハッシュ値の読み書きは O(1) の操作です。つまり非常に高速で、特にループ処理と比較すると顕著です。

それでもループは2つ残っています:

ひとつはハッシュテーブルを構築するため、もうひとつは検証するためのものです。しかし、これらのループはネストしていないため、このアルゴリズムは O(n) になります。

実際に3つの解法をベンチマークすると、分析結果と一致することがわかります:

hash    1.216667   0.000000   1.216667 (  1.216007)
sub     6.240000   1.023333   7.263333 (  7.268173)
count 222.866644   0.073333 222.939977 (223.440862)

折れ線グラフで可視化すると次のようになります。

いくつか注目すべき点があります:

1. Y軸(縦軸)は処理完了までにかかった秒数、X軸(横軸)は入力サイズを表しています。
2. このグラフは対数スケールのため、一定範囲の値が圧縮されています。実際には count の線はもっと急峻です。
3. 対数グラフにした理由は、面白い現象を見てもらうためです。入力サイズが非常に小さい場合は、なんと count 版の方が速いのです!

まとめ

今回は、アルゴリズムの時間計算量、Big O記法、そして計算量の分析方法について学びました。また、同じ問題に対する複数の解法を比較し、それぞれの性能を分析しました。

新しい発見や学びがあったなら嬉しい限りです!

もし参考になった場合は、ぜひSNSでこの記事をシェアしてください。また、ニュースレターを未購読の方は購読いただければ、今後も同様のコンテンツをお届けします。

最後までお読みいただきありがとうございました。