電子メール アドレス「demensdeum@gmail.com」が、手紙の受信が許可されている電子メール アドレスのリストに含まれているかどうかを確認する必要があるとします。 .
最初の要素から最後の要素までリスト全体を調べて、その要素が指定されたアドレスと等しいかどうかを確認してみましょう –線形探索アルゴリズムを実装してみましょう。しかし、これには長い時間がかかりますか?
この質問に答えるには、「アルゴリズムの時間計算量」の「O」表記を使用します。最悪の場合の線形探索の動作時間は配列要素の n 番目の数に等しいので、これを「O」表記で書きましょう –の上）。次に、既知のアルゴリズムには 3 つのパフォーマンス指標があることを説明する必要があります。最良の場合、最悪の場合、および平均的な場合の実行時間。たとえば、メール アドレス「demensdeum@gmail.com」は配列の最初のインデックスにあり、次の最初のステップで見つかります。このアルゴリズムを使用すると、実行時間はせいぜい – ということになります。 O(1);そして、リストの最後にある場合、これは最悪のケースです。 O(n)
しかし、ソフトウェアの実装やハードウェアのパフォーマンスの詳細についてはどうなのでしょうか?それらは Big O に影響を与えるはずです。ここで一呼吸置いて、時間計算量の計算が、このアルゴリズムのみが存在し、他には何も存在しない、抽象的な理想的なマシンに対して計算されると想像してください。
アルゴリズム
OK、線形探索はかなり遅いことがわかりました。二分探索を使ってみましょう。まず、バイナリ データを処理しないことを明確にしておきます。この名前は、その動作の特殊性のためにこのメソッドに付けられました。最初に配列を 辞書編集順の場合、アルゴリズムは配列全体の範囲を取得し、範囲の中央の要素を取得し、それを比較します辞書順に基づいて、比較の結果に応じて、さらに検索するためにどの範囲を使用するかを決定します。現在の上半分または下半分。つまり、各検索ステップで、可能な 2 つの候補から決定が行われます。バイナリロジック。このステップは、単語が見つかるか見つからない (範囲の下位インデックスと上位インデックスの交差が発生する) まで繰り返されます。
このアルゴリズムのパフォーマンス –最良のケースは要素が配列 O(1) の中央ですぐに見つかった場合であり、列挙の最悪のケースは O(log n) です。
落とし穴
二分探索を実装する際、 プログラミング言語ライブラリにおける辞書編集の比較の標準化が欠如という興味深い問題に遭遇しただけでなく、 実装のための統一標準が存在しないことさえ発見しました。 localeJavaScript 内で比較します。 ECMAScript 標準では、この関数のさまざまな実装が許可されています。そのため、localeCompare を使用して並べ替える場合、異なる JavaScript エンジンではまったく異なる結果が観察される可能性があります。
したがって、アルゴリズムが正しく機能するには、同じ辞書編集比較アルゴリズムのみを並べ替えて使用する必要があり、そうでないと何も機能しません。しかし、たとえば、ある実装の独自のソート/ソートを実装せずに、Scala で配列をソートし、nodejs を使用して検索しようとすると、人間性への失望以外に何も待つことはありません。
ソース
辞書編集的比較とは何ですか?また、それは何を表しますか?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript
ソースコード
https://gitlab.com/demensdeum/algorithms
