Big O Notation —イラストとビデオで簡単に説明

Big O表記は、アルゴリズムの速度を伝えるために使用されます。これは、他の人のアルゴリズムを評価するとき、および自分のアルゴリズムを評価するときに重要になる可能性があります。この記事では、Big O表記とは何かを説明し、それを使用するアルゴリズムの最も一般的な実行時間のリストを示します。

アルゴリズムの実行時間はさまざまな速度で増加します

私の息子ユダはたくさんのおもちゃを持っています。実際、彼は10億のおもちゃを手に入れました!子供が家族の両側で最初の孫である場合、子供がどれほど早くたくさんのおもちゃを手に入れることができるかに驚かれることでしょう。??

とにかく、ユダには問題があります。彼の友達が訪れて特定のおもちゃで遊びたいとき、おもちゃを見つけるのに永遠にかかることがあります。そこで彼は、特定のおもちゃをできるだけ早く見つけるのに役立つ検索アルゴリズムを作成したいと考えています。彼は、単純検索とバイナリ検索という2つの異なる検索アルゴリズムのどちらかを決定しようとしています。 (これらのアルゴリズムに精通していなくても心配しないでください。)

選択するアルゴリズムは、高速かつ正確である必要があります。一方では、バイナリ検索はより高速です。そして、ユダは、友人がおもちゃを探すのに飽きるまで、たった30しかありません。一方、単純な検索アルゴリズムは記述が簡単で、バグが発生する可能性は低くなります。彼の友人が彼のコードにバグを見つけたら、それは確かに恥ずかしいことです!特に注意するために、ユダは両方のアルゴリズムの時間を100個のおもちゃのリストで計ることにしました。

1つのおもちゃをチェックするのに1ミリ秒かかると仮定しましょう。簡単な検索では、ユダは100個のおもちゃをチェックする必要があるため、検索の実行には100ミリ秒かかります。一方、彼は二分探索で7つのおもちゃをチェックするだけで済みます(log2 100は約7です。この記事の要点ではないので、この計算が混乱しても心配しないでください)。そのため、検索には7ミリ秒かかります。走る。しかし実際には、リストには10​​億個のおもちゃが含まれます。もしそうなら、簡単な検索にはどれくらい時間がかかりますか?二分探索にはどのくらい時間がかかりますか?

100要素のリストを使用した単純検索とバイナリ検索の実行時間

ユダは10億個のおもちゃで二分探索を実行し、30ミリ秒かかります(log2 1,000,000,000は約30です)。「32ミリ秒!」彼が考えている。「単純検索は100要素で100ミリ秒かかり、バイナリ検索は7ミリ秒かかったため、バイナリ検索は単純検索よりも約15倍高速です。簡単な検索には30×15 = 450ミリ秒かかりますよね?友達が退屈するのに30秒もかかりません。」ユダは簡単な検索で行くことにしました。それは正しい選択ですか?

いいえ。結局のところ、ユダは間違っていて、一生友達を失いました。?10億アイテムの単純検索の実行時間は10億ミリ秒、つまり11日です。問題は、バイナリ検索と単純検索の実行時間が同じ速度で増加しないことです。

実行時間は非常に異なる速度で増加します!アイテムの数が増えると、バイナリ検索の実行には少し時間がかかりますが、単純な検索の実行にはかなり時間がかかります。したがって、数値のリストが大きくなると、バイナリ検索は単純な検索よりも突然はるかに高速になります。

ですから、ユダは二分探索が単純な探索より常に15倍速いということについて間違っていました。10億個のおもちゃがあるとすると、3300万倍も速くなります。

リストのサイズが大きくなると、実行時間がどのように長くなるかを知ることは非常に重要です。そこで、BigO表記が登場します。

Big O表記は、アルゴリズムの速度を示します。たとえば、サイズnのリストがあるとします。単純検索では各要素をチェックする必要があるため、n回の操作が必要になります。Big O表記の実行時間はO(n)です。

秒はどこですか?何もありません— BigOは速度を秒単位で教えてくれません。Big O表記を使用すると、操作の数を比較できます。アルゴリズムがどれだけ速く成長するかを示します。

別の例を見てみましょう。バイナリサーチは、ログ必要とn個のサイズのリストを確認するための操作をn個。Big O表記の実行時間はどれくらいですか?O(log n)です。一般的に、BigO表記は次のように記述されます。

これは、アルゴリズムが実行する操作の数を示します。操作数の前に「ビッグO」を付けるので、ビッグO表記と呼ばれます。

BigOは最悪の場合の実行時間を確立します

単純な検索を使用して、ユーザーデータベースでユーザーを検索するとします。単純な検索の実行にはO(n)時間がかかることを知っています。つまり、最悪の場合、アルゴリズムはデータベース内のすべてのユーザーを調べる必要があります。この場合、「aardvark213」という名前のユーザーを探しています。これはリストの最初のユーザーです。したがって、アルゴリズムはすべてのエントリを調べる必要はありませんでした。最初の試行でそれが見つかりました。アルゴリズムはO(n)時間かかりましたか?それとも、最初の試行でその人を見つけたので、O(1)時間かかりましたか?

単純な検索でもO(n)時間かかります。この場合、アルゴリズムは探していたものを即座に見つけました。これが最良のシナリオです。しかし、Big O表記は、最悪のシナリオに関するものです。したがって、最悪の場合、アルゴリズムはデータベース内のすべてのユーザーを1回調べる必要があると言えます。それはO(n)時間です。これは安心です。単純な検索がO(n)時間より遅くなることは決してないことをご存知でしょう。

いくつかの一般的なBigOの実行時間

これは、あなたが頻繁に遭遇する5つのBig O実行時間であり、最も速いものから最も遅いものへとソートされています。

  • O(log n)、ログ時間とも呼ばれます。例:二分探索。
  • O(n)、線形時間とも呼ばれます。例:単純な検索。
  • O(n * log n)。例:クイックソートのような高速ソートアルゴリズム。
  • O(n 2)。例:選択ソートのような遅いソートアルゴリズム。
  • O(n!)。例:巡回セールスマンのように、非常に遅いアルゴリズム。

さまざまなBigOの実行時間を視覚化する

16個のボックスのグリッドを描画していて、5つの異なるアルゴリズムから選択できるとします。最初のアルゴリズムを使用する場合、グリッドを描画するのにO(log n)時間がかかります。1秒間に10回の操作を実行できます。O(log n)時間の場合、16個のボックスのグリッドを描画するのに4回の操作が必要です(log 16 base 2は4です)。したがって、グリッドを描画するのに0.4秒かかります。1,024個のボックスを描画する必要がある場合はどうなりますか?1,024 = 10回の操作、つまり1,024個のボックスのグリッドを描画するのに1秒かかります。これらの数値は最初のアルゴリズムを使用しています。

2番目のアルゴリズムは低速です。O(n)時間がかかります。16個のボックスを描画するには16回の操作が必要であり、1,024個のボックスを描画するには1,024回の操作が必要です。それは秒単位でどのくらいの時間ですか?

残りのアルゴリズムのグリッドを最速から最遅まで描画するのにかかる時間は次のとおりです。

他の実行時間もありますが、これらは最も一般的な5つです。

これは単純化です。実際には、Big Oの実行時間から多くの操作にこれほどうまく変換することはできませんが、これは適切な見積もりです。

結論

主なポイントは次のとおりです。

  • アルゴリズムの速度は秒単位ではなく、操作数の増加で測定されます。
  • 代わりに、入力のサイズが大きくなるにつれて、アルゴリズムの実行時間がどれだけ速く増加するかについて説明します。
  • アルゴリズムの実行時間はBigO表記で表されます。
  • O(log n)はO(n)よりも高速ですが、検索するアイテムのリストが増えるにつれて、はるかに高速になります。

そして、これはこの記事とそれ以上にあるものの多くをカバーするビデオです。

この記事がBigO表記についてより明確になったことを願っています。この記事は、Algorithms inMotionと呼ばれるManningPublicationsのビデオコースのレッスンに基づいています。このコースは、AditBhargavaによる素晴らしい本GrokkingAlgorithmsに基づいています。この記事で楽しいイラストをすべて描いたのは彼です。

あなたが本を通して最もよく学ぶならば、本を手に入れてください!ビデオを通じて最もよく学ぶ場合は、私のコースを購入することを検討してください。コード「39carnes」を使用すると、私のコースが39%オフになります。