RubyでBig-O表記を調べる

線形探索アルゴリズムのBig-O分析を行いましょう。線形検索はデータセットの先頭から始まり、ターゲット要素が見つかるまでトラバースします。

これがRubyでの実装です。

def find_number_via_linear_search(array, target)
  counter = 0 

  # iterate through the given array starting 
  # at index 0 and continuing until the end 
  while counter < array.length 
    if array[counter] == target 
      # exit if target element found 
      return "linear search took: #{counter} iterations" 
    else 
      counter += 1 
    end 
  end 

  return "#{target} not found" 
end 

このメソッドに次のようなスピンを与えることができます：

# Let's create an array with 50 integers
# and then re-arrange the order to make
# things more interesting
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"

関数のBig-O表記を分析するときは、最悪の場合のシーンリオ（別名：漸近線の上限）に注意します。

これを直感的に考えると、反復の最小数は1になります。これは、ターゲット要素が配列の0の位置にあるときに発生します。反復の最大数（または最悪の場合のシーンリオ）は50です。これは、ターゲット要素が配列に見つからなかった場合に発生します。

配列に100個の要素がある場合、最悪の場合は100回の反復になります。 200要素？ 200回の反復。したがって、線形探索のBig-O表記は単純にO（n）です。ここで、nは要素の数です。

二分探索を使用したより複雑な例！

次に二分探索について考えてみましょう。 事前に並べ替えられたのバイナリ検索を行う方法は次のとおりです。 配列：1。真ん中の要素を取る
2. element == targetの場合 完了しました3。 element > targetの場合 配列の上半分を破棄します4。element < targetの場合 アレイの下半分を破棄します。5。残りのアレイで手順1からやり直します

注：Rubyistの場合は、このアルゴリズムを実装する組み込みのb-searchメソッドがあります。

たとえば、辞書があり、世界の「パイナップル」を探しているとします。辞書の真ん中のページに行きます。たまたま世界が「パイナップル」だったら、もう終わりです！

しかし、私の推測では、辞書の真ん中はまだ「p」に含まれていないので、「ラマ」という単語が見つかるかもしれません。文字「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回分割する必要がありました。

これを一般化すると、二分探索の最悪の場合のシーンリオは、配列を半分に分割できる最大回数に等しいと言えます。

数学では、対数を使用して、「この数を取得するために、この数のいくつを乗算しますか？」という質問に答えます。問題に対数を適用する方法は次のとおりです。

したがって、Big-O、つまりバイナリ検索の最悪の場合の実行時間はlog（base 2）nであると言えます。