3

たとえば、O(n) のアルゴリズムと、償却された O(n) のアルゴリズムがあるとします。厳密に言えば、非償却アルゴリズムは常に償却アルゴリズムと同じかそれよりも高速であると言えますか? または、償却バージョンを好む理由はありますか (コードの単純さや実装の容易さなどを無視します)?

4

6 に答える 6

7
  1. Big O 表記は、コードがどのようにスケーリングされるかを示すだけで、有限の N に対してどれだけ高速になるかは示しません。
  2. 償却済みと非償却の違いは、最悪の場合のパフォーマンスやレイテンシ (リアルタイム システムやインタラクティブ システムなど) を考慮する場合に重要です。ただし、平均スループットのみを気にする場合、それらはすべての実用的な目的で同じです。償却分析は、科学計算や大規模なデータ マイニングなど、パフォーマンスが非常に重要な状況でも十分に機能します。
于 2010-02-22T01:51:24.770 に答える
6

または、償却されたバージョンを好む理由はありますか

より小さな定数。

于 2010-02-22T01:36:43.453 に答える
5

O(n) アルゴリズムと償却 O(n) アルゴリズムの主な違いは、償却 O(n) アルゴリズムの最悪の場合の動作について何も知らないことです。実際には、それはあまり重要ではありません。アルゴリズムが何度も実行されている場合、平均の法則を当てにして、いくつかの悪いケースを相殺することができます。また、アルゴリズムがあまり頻繁に実行されていない場合は、その場合、最悪のケースに遭遇する可能性はまったくありません。

「償却」という言葉が重要になる唯一のケースは、何らかの理由で時折のパフォーマンスの低下を受け入れることができない場合です。たとえば、GUI アプリケーションでは、ユーザーがそこに座って退屈している間に速度が落ちたり応答を停止したりしないという保証と引き換えに、平均的なケースのパフォーマンスを喜んであきらめます。このようなアプリケーションでは、最悪の場合の動作であっても、GUI の応答を停止させる可能性のあるコードに対して適切であることを確認する必要があります。

それでも、ほとんどの場合、償却された O(n) 対 O(n) を心配する必要はなく、代わりに定数要因が何であるかを心配することができます (他の人が既に言ったように)。

于 2010-02-22T02:05:58.367 に答える
1

償却アルゴリズムの必要性の古典的な例は、挿入が償却 O(1) される std::vector です。

償却アルゴリズムを使用するいくつかの理由:

  • はるかに効率的な平均的なケース。
  • より簡単な実装。
  • 最悪の場合の保証アルゴリズムは存在しません。
于 2010-02-22T01:51:42.270 に答える
1

Big O 表記は、入力の増加に伴ってアルゴリズムがどのように変化するかを示します。コードをプロファイリングするためのショートカットではありません。

O(n) にはより大きな定数があるため、プログラム内のすべての n に対して O(n^2) の方が優れたアルゴリズムである可能性があります。

したがって、アルゴリズムの選択は、入力サイズに対してどのアルゴリズムがより高速であるかに大きく依存します。あなたの質問への答えは、プログラムで両方のアルゴリズムをプロファイルし、どちらが速いかを判断することだと思います。

于 2010-02-22T01:37:39.757 に答える
0

厳密に言えば、big-O は、O(n) を使用するアルゴリズムが、償却された O(n) を使用するアルゴリズムよりも高速であると言えるほど正確な尺度ではありません。考えてみてください。複雑さの分析で忠実度を下げると、定数係数が大きく異なり、償却バージョンが速くなる可能性があります。

また、償却の影響は用途に依存する傾向があります。たとえば、ハッシュ テーブルを使用している場合、償却の影響は get 操作と add 操作の比率に大きく依存します。したがって、1000 エントリを追加してから 10 億回のルックアップを行った場合、数回再ハッシュしなければならなかったという事実は、大きな違いにはなりません。ただし、常にエントリを追加している場合は、再ハッシュのコストが加算される可能性があります。

そのため、償却は最悪のケースとは異なります。Big-O は最悪のケースを反映していますが、償却により、「x ごとに 1 つがヒットし、x は問題にならないほど十分に大きい」と言えます。また、ハッシュ テーブルへの挿入などの例を考えると、x は何らかの定数に従って大きくなります。したがって、100 個のバケットで始まり、再ハッシュごとに 2 倍になるハッシュ テーブルがある場合、再ハッシュは漸近的にどんどん離れていきます。さらに、償却された複雑さを持つアルゴリズムの絶対的な最悪のケースの複雑さは、以前の呼び出しに依存しますが、平均的なケースのような測定では、呼び出しは独立していると見なされます。

于 2010-02-22T02:48:03.733 に答える