ウィキペディアによると、「通常、正確な最悪のシナリオを決定することは不可能です。代わりに、シナリオは、少なくとも最悪のケースと同じくらい悪いと見なされます」. その部分がわかりません。リスト内の数値を検索するときの最悪のケースは、それが最後のインデックスにあるときではありませんか? まさに最悪のケースではないでしょうか。
3 に答える
5
エントリーを読み間違えたようです。http://en.wikipedia.org/wiki/Best,_wost_and_average_case
彼らは、最悪のケースは特定できるものかもしれないと言っていますが、正確な入力はそうではありません. たとえば、バケットを使用してハッシュ テーブル / ディクショナリを実装する場合、100 個のサンプル エントリすべてが同じバケットにハッシュされる場合が最悪のケースであると言うのは簡単ですが、実際に同じバケットにハッシュされる 100 個の入力を識別するのはそれほど簡単ではありません。一部のアルゴリズムでは、最悪の場合の正確な入力データを導き出すことがほとんど不可能な場合があります。
最悪の場合の分析にも同様の問題があります。通常、正確な最悪のシナリオを特定することは不可能です。代わりに、少なくとも最悪のケースと同じくらい悪いシナリオが考慮されます。たとえば、アルゴリズムを分析するとき、このパスを生成する正確な入力を決定することができなくても、(たとえば、ループの最大数を考慮することによって) アルゴリズムを介して可能な限り長いパスを見つけることができる場合があります(実際、そのような入力は存在しない可能性があります)。これにより、安全な分析が得られますが (最悪のケースが過小評価されることはありません)、このパスを必要とする入力がない可能性があるため、悲観的な分析になります。
于 2012-09-11T19:00:30.857 に答える
0
はい、それはあなたが言及したシナリオの正確な最悪のケースですが、あなたが言及したシナリオは単純なシナリオです。
ルートまでノードを回転させる複雑な操作を想像してみてください。最悪のケースは、ツリーの現在の状態の複雑な関数である場合があります。しかし、たとえば、O(log(N)) または O(N) ローテーションを実行する必要があることは、どちらかが最悪の場合よりも最悪であることを証明できるかどうかに応じて、はるかに簡単に想像できます (確かに O(N) はこのより複雑なシナリオでは、最悪の場合にバインドされます)。
于 2012-09-11T18:59:22.940 に答える
0
最悪の場合の実行時間 (WCET) を計算するには、入力サイズに関して各ループを考慮し、ループが早期に終了しないと仮定します。ただし、多少複雑なアルゴリズムを使用している場合は、WCET につながる入力が計算されないことがあります。たとえば、アルゴリズムで (名前の) ハッシュ テーブルを使用する場合、すべてのキーが同じセルにハッシュされると想定できますが、どのような種類の入力がこのケースにつながるかはわかりません。入力セマンティクスがそのようなハッシュ テーブルにつながらないことを確認することさえ可能かもしれませんが、それでも、すべてのキーが同じハッシュを持つという仮定に基づいて WCET を計算します。
于 2012-09-11T19:06:11.800 に答える