作成されたいくつかのアルゴリズムで最悪の実行時の複雑さの順序を取得しようとしています。しかし、アルゴリズムの基本操作の間違った量または間違った量を選択し続ける傾向があるという問題に遭遇しました。
私には、基本的な操作の選択は、科学というより芸術のように思えます。私のテキストボックスをグーグルで読んだ後、私はまだ良い定義を見つけていません. これまでは、比較や配列操作などの「アルゴリズム実行内で常に発生する操作」と定義してきました。
しかし、アルゴリズムには多くの場合、常に実行される多くの比較があるため、どの操作を選択しますか?
私はある程度それが芸術であることに同意するので、ドキュメントなどを書くときは常に明確にする必要があります.しかし、通常、それは基礎となるデータ構造への「訪問」です。あなたが言ったように、配列の場合は比較またはスワップであり、ハッシュマップの場合はキーの手動検査である可能性があり、グラフの場合は頂点またはエッジへの訪問などです.
これは、実際にアルゴリズムを実装した場合にのみ機能しますが、プロファイラーを使用して、どの操作がボトルネックであるかを確認できます。それは実用的な観点です。理論的には、基本的な操作ではないものはすべてゼロ時間で実行されると想定する人もいます。
私が聞いたやや単純な定義は次のとおりです。
アルゴリズム内の他の操作と少なくとも同じ回数実行される操作。
たとえば、並べ替えアルゴリズムでは、ほとんどの場合、並べ替えの前に要素にアクセスして「チェック」する必要があるため、これらは割り当てではなく比較になる傾向がありますが、チェックによって並べ替えが行われない場合があります。したがって、少なくとも割り当てと同じ数の比較が常に存在します。