最悪/平均/最良のケースがアルゴリズムの関数への複雑な時間を決定するために使用されることを理解していますが、それは漸近解析でどのように使用されますか? 上限/タイト/下限（大きなO、大きなオメガ、大きなシータ）が2つの関数を比較するために使用され、nが増加するにつれて限界（成長）が他のものにどのように見えるかを確認するために使用されることを理解していますが、ワースト/平均/ベスト ケースのビッグ O と漸近分析の違い。ワースト/平均/ベストケースのビッグ O を漸近解析と測定境界に代入することから、正確には何が得られるでしょうか? ワースト/平均/ベスト ケースのビッグ O の 2 つのアルゴリズムを具体的に比較するために、漸近解析を使用しますか? その場合、アルゴリズム 1 に関数 f(n) を使用し、アルゴリズム 2 に g(n) を使用しますか、またはアルゴリズム 1 が f(n) であるアルゴリズムごとに個別の漸近分析を行い、いくつかの c*g(n を見つけようとします。 ) そのような => f(n) およびそのような c*g(n) <= f(n) そして、アルゴリズム 2 に対して同じことを行います。私はここで全体像を見ていません。
質問する
1836 次
3 に答える
4
あなたは全体像が欲しいので、同じことをさせてください。
漸近分析は、入力のサイズが増加するにつれて実行時間がどのように増加するかを調査するために使用されます。ソートの場合)、ノード数 (グラフの場合)、またはビット数の偶数 (2 つの数値の乗算の場合)。
漸近解析を扱うとき、私たちの目標は、特定のケースでどのアルゴリズムがよりうまく機能するかを見つけることです。アルゴリズムは、同じサイズの入力であっても、非常にさまざまな時間で実行されることを理解してください。ソートされた数字のリストを yuo に渡した場合、あなたは何もしなくて済みます。逆にソートされた数字のリストを渡した場合、必要な操作の数を想像してみてください。これを見て、入力がどのようなケースになるかを知る方法が必要であることに気付きましたか?それは最良のケースでしょうか?最悪のケースの入力を得るでしょうか?これに答えるには、いくつかの入力が必要です入力の分布に関する知識。すべてが最悪のケースでしょうか?それとも平均的なケースでしょうか?それともほとんどが最良のケースでしょうか?
ほとんどの場合、入力分布の知識を確認するのはかなり困難です。その場合、2 つのオプションが残されます。常に平均的なケースを想定してアルゴリズムを分析するか、実行中のケースに関係なく実行中のケースで保証を得ることができます。入力分布。前者は平均ケース分析と呼ばれ、そのような分析を行うには、平均ケースを構成するものを正式に定義する必要があります。定義が難しい場合があり、多くの数学的洞察が必要です。すべてのトラブルはそれだけの価値があります。いくつかのアルゴリズムが、最悪の場合の実行時間と比較して、平均的なケースではるかに高速に実行されることがわかっている場合.これを証明するランダム化されたアルゴリズムがいくつかあります.そのような場合、平均的なケースの分析を行うと、その実用的な適用性が明らかになります. 後者、
ええ、あなたは考えていますよね?それほど直感的ではありません。
常に最良のケースが得られるとは限らないため、最良のケースの分析はめったに使用されません。それでも、そのような分析を実行して興味深い動作を見つけることができます。
結論として、解決したい問題がある場合、アルゴリズムを考え出します。アルゴリズムができたら、それが状況に実際に役立つかどうかを判断する必要があります。適用し、それらの時間と空間の複雑さに基づいて比較します。比較する指標は他にもある可能性がありますが、これら 2 つは基本的なものです。そのような指標の 1 つは、実装の容易さである可能性があります。そして、目の前の状況に応じて、どちらかの最悪のケースを採用します。たとえば、最悪のケースのシナリオがめったにない場合は、平均的なケースの分析を実行する方がはるかに理にかなっています。ただし、コードのパフォーマンスが重要な性質のものであり、厳密な時間制限で出力する場合は、最悪のケースの分析を検討する方がはるかに賢明です.したがって、あなたが行う分析は目の前の状況に依存し、時間が経つにつれて、どの分析を適用するかの直感が第二の性質になります。
さらに質問がある場合はお尋ねください。
于 2013-08-12T08:59:56.730 に答える