Loading article…
コンピュータサイエンスでは、与えられたアルゴリズムの最良、最悪、平均ケースは、それぞれリソース使用量が最小、最大、平均でどのくらいであるかを表します。通常、考慮されるリソースは実行時間、つまり時間計算量ですが、メモリやその他のリソースの場合もあります。最良ケースは、n個の要素を持つ入力データに対して最小のステップ数を実行する関数です。最悪ケースは、n個の要素を持つ入力データに対して最大のステップ数を実行する関数です。平均ケースは、n個の要素を持つ入力データに対して平均的なステップ数を実行する関数です。[ 1 ]
リアルタイムコンピューティングにおいては、アルゴリズムが常に時間内に完了することを保証するために、最悪の場合にどれくらいの時間が必要になるかを把握することが重要であるため、最悪の場合の実行時間は特に懸念されることが多い。
アルゴリズム解析では、平均性能と最悪性能が最もよく用いられます。最良性能はあまり一般的ではありませんが、用途はあります。例えば、個々のタスクの最良ケースが分かっている場合、それらを用いて全体的な最悪ケース解析の精度を向上させることができます。 コンピュータ科学者は、確率解析手法、特に期待値を用いて、期待実行時間を決定します。
これらの用語は他の文脈でも使用されます。例えば、伝染病の最悪シナリオと最良シナリオ、電子回路素子がさらされる最悪温度などです。特定の許容誤差を持つ部品を使用する場合、デバイスは許容誤差と外部条件の最悪の組み合わせでも適切に動作するように設計する必要があります。
コンピュータサイエンスにおいて、 「ベストケース性能」という用語は、アルゴリズムが最適な条件下でどのように動作するかを説明するために用いられます。例えば、リストに対する単純な線形探索において、目的の要素がリストの最初の要素である場合がベストケースとなります。
アルゴリズムの開発と選択は、最良ケースのパフォーマンスに基づいて行われることはほとんどなく、ほとんどの学術機関や企業は、平均ケースの複雑さと 最悪ケースのパフォーマンスの向上に関心を持っています。また、アルゴリズムは、有限個の入力に対して解をハードコーディングすることで、最良ケースの実行時間を改善するように簡単に変更できるため、この指標はほとんど意味をなさなくなります。[ 2 ]
最悪ケースのパフォーマンス分析と平均ケースのパフォーマンス分析にはいくつかの類似点があるが、実際には通常、異なるツールとアプローチが必要となる。
典型的な入力が何を意味するのかを判断するのは難しく、多くの場合、その平均的な入力は数学的に特徴付けるのが難しい特性を持っています（たとえば、テキスト文字列を操作するように設計されたアルゴリズムを考えてみてください）。同様に、特定の「平均的なケース」（おそらくアルゴリズムの一部の使用にのみ適用可能）の適切な記述が可能であっても、それらは方程式の分析をより困難にする傾向があります。[ 3 ]
最悪ケース分析は安全な分析（最悪のケースを過小評価しない）を提供するが、これほど多くのステップを要する（現実的な）入力が存在しない可能性があるため、過度に悲観的になる可能性がある。
状況によっては、安全性を確保するために悲観的な分析を用いる必要がある場合もあります。しかしながら、悲観的な分析は往々にして悲観的すぎる場合があるため、実際の値に近づきつつも楽観的な分析（例えば、既知の低い故障確率を考慮した分析）の方がはるかに実用的なアプローチとなることがあります。学術理論における、最悪ケース分析と平均ケース分析の間のギャップを埋める現代的なアプローチの一つに、平滑化分析があります。
処理に要する時間は短いものの、周期的に非常に長い時間を要するアルゴリズムを分析する場合、償却分析を用いることで、（場合によっては無限に続く）一連の操作における最悪の実行時間を求めることができます。この償却コストは平均コストに非常に近い値となり、同時に実行時間の上限値も保証されます。例えば、オンラインアルゴリズムはしばしば償却分析に基づいて構築されています。
最悪ケースの性能が悪いアルゴリズムの多くは、平均ケースの性能が良い。私たちが解決したい問題においては、これは良いことである。つまり、私たちが関心を持つ特定のインスタンスが平均的なものであることを期待できるからだ。しかし、暗号学においては、これは非常に悪いことである。暗号問題の典型的なインスタンスは困難であるべきだからだ。このような場合、ランダム自己還元性などの手法を特定の問題に適用することで、最悪ケースが平均ケースよりも難しくない、あるいは同等に、平均ケースが最悪ケースよりも簡単でないことを示すことができる。
一方、ハッシュテーブルのようなデータ構造の中には、最悪の場合の動作が非常に悪いものもありますが、適切に記述され、十分なサイズのハッシュテーブルであれば、統計的に最悪のケースが発生することはありません。実行される操作の平均数は指数関数的に減少するため、操作の実行時間は統計的に制限されます。
