私は、作成された2つのアルゴリズムで最悪の実行時の複雑さの順序を取得しようとしています。しかし、私はアルゴリズムの基本的な操作の間違った量や間違った量を選択し続けるという問題にぶつかってきました。実行時の複雑さを計算する際に基本的な操作を知るにはどうすればよいですか？
私には基本的な動作の選択は、科学よりも芸術のよりであることのように見えます。グーグルのテキストボックスをグーグルで読んだ後、私はまだ良い定義を見つけていません。これまでは、これを「アルゴリズム実行中に常に発生する操作」（比較や配列操作など）と定義しました。
しかし、アルゴリズムは、多くの場合、常に実行されているので、あなたがどの操作を選んでください多くの比較を持っていますか？
は、私はそれが芸術だある程度に同意することになるので、などのドキュメントを、書くときは、常に明確にすべき..しかし、通常は基礎となるデータ構造への「訪問」です。あなたが言ったように、配列の比較やスワップ、ハッシュマップの場合はキーの手動検査、グラフの場合は頂点やエッジなどへのアクセスです。
これは動作します実際にアルゴリズムを実装したときに、プロファイラを使用してどの操作がボトルネックであるかを知ることができます。それは実用的な視点です。理論的には、基本的な操作ではないすべてがゼロ時間で実行されると仮定する人もいます。
でも練習複雑さの理論家は、この種のものについての意見の相違を持っているので、以下は少し主観的なことがありますhttp://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.htmlは
ビッグO記法の目的は、読者のためのアルゴリズムの効率を要約することです。実用的な文脈では、big-O定数が極端に小さくても大きくなくても（メモリ階層の影響を無視して）仮定すると、アルゴリズムがどれくらいのクロックサイクルを要するかということに最も関心があります。これはリンクされたポストで言及された "単価"モデルです。
アルゴリズムをソートするための比較をカウントする理由は、比較のコストは、入力データの種類に依存していることです。ソートアルゴリズムはO（c n log n）サイクルを要し、ここでcは比較の費用ですが、アルゴリズムによって実行される他の作業はO（n log n）なので、比較をカウントする方が簡単です。 n^2のlog nステップとn^2の比較で長さnのn個のソートされた配列の連結をソートするソートアルゴリズムがあります。ここでは、どちらも必ずしも他を支配するものではないので、比較数と計算上のオーバーヘッドを別々に述べることが期待されます。
私が聞いたことが多少簡単な定義は次のとおりです。
アルゴリズムでは、他の 操作と少なくとも同じ何度も実行される操作。
たとえば、並べ替えアルゴリズムでは、並べ替えのアルゴリズムは、並べ替えの前にほとんど常に「チェック」して要素をチェックしなければならないため、割り当てではなく比較となる傾向があります。再注文する。だから、常に割り当てと同じくらい多くの比較があります。