例で説明されたビッグO表記

Big O表記は、特定のアルゴリズムの速度または複雑さを説明する方法です。現在のプロジェクトで事前定義されたアルゴリズムが必要な場合は、他のオプションと比較してどれだけ速いか遅いかを理解することが重要です。

Big O表記とは何ですか?どのように機能しますか?

簡単に言えば、Big O表記は、アルゴリズムが実行する操作の数を示します。推定操作数の前にある文字通りの「BigO」からその名前が付けられています。

Big O表記では、アルゴリズムの速度(秒単位)がわかりません。アルゴリズムの実行にかかる時間に影響を与える要因は多すぎます。代わりに、Big O表記を使用して、実行する操作の数によってさまざまなアルゴリズムを比較します。

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

あなたがジェーンという名前の生徒を持つ教師だと想像してみてください。彼女の記録を見つけたいので、簡単な検索アルゴリズムを使用して学区のデータベースを調べます。

単純な検索の実行にはO(n)回かかることをご存知でしょう。これは、最悪の場合、ジェーンを見つけるためにすべてのレコード(nで表される)を検索する必要があることを意味します。

しかし、単純な検索を実行すると、ジェーンのレコードがデータベースの最初のエントリであることがわかります。すべてのエントリを確認する必要はありません。最初の試行で見つかりました。

このアルゴリズムはO(n)時間かかりましたか?それとも、最初の試行でジェーンのレコードを見つけたので、O(1)時間かかりましたか?

この場合、0(1)が最良のシナリオです。Janeのレコードがトップになったことは幸運でした。ただし、Big O表記は、単純な検索の場合は0(n)である最悪のシナリオに焦点を当てています。単純な検索がO(n)時間より遅くなることは決してないというのは安心です。

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

学区のデータベースの各要素をチェックするのに1ミリ秒かかると仮定します。

簡単な検索では、10個のエントリをチェックする必要がある場合、実行に10ミリ秒かかります。しかし、二分探索アルゴリズムでは、3つの要素をチェックするだけで済み、実行には3ミリ秒かかります。

ほとんどの場合、検索する必要のあるリストまたはデータベースには、数百または数千の要素が含まれます。

10億の要素がある場合、単純な検索の使用には最大10億ミリ秒、つまり11日かかります。一方、バイナリ検索の使用は、最悪のシナリオではわずか32ミリ秒かかります。

明らかに、単純検索とバイナリ検索の実行時間はほぼ同じ速度で増加しません。エントリのリストが大きくなると、バイナリ検索の実行に少し時間がかかります。単純検索の実行時間は、エントリのリストが増えるにつれて指数関数的に増加します。

これが、リストサイズに関連して実行時間がどのように増加するかを知ることが非常に重要である理由です。そして、これはまさにBigO表記が非常に役立つところです。

BigO表記は操作の数を示します

上記のように、Big O表記は、アルゴリズムが実行される時間を示しません。代わりに、実行する操作の数が表示されます。アルゴリズムの成長速度を示し、他のアルゴリズムと比較することができます。

BigO表記での一般的なアルゴリズムとその実行時間は次のとおりです。

ビッグO表記アルゴリズムの例
O(log n)二分探索
オン)簡単な検索
O(n * log n)クイックソート
O(n2)選択ソート
オン!)巡回セールスマン

これで、BigO表記で危険なことを十分に理解できました。そこに出て、アルゴリズムの比較を開始します。