最良、最悪、平均のケース

コンピュータサイエンスでは、特定のアルゴリズムの最良、最悪、平均のケースは、それぞれ、リソース使用量が少なくとも、最大で、平均で であることを表します。通常、考慮されるリソースは実行時間、つまり時間計算量ですが、メモリやその他のリソースである場合もあります。最良のケースは、n 要素の入力データに対して最小数のステップを実行する関数です。最悪のケースは、サイズ n の入力データに対して最大数のステップを実行する関数です。平均的なケースは、n 要素の入力データに対して平均的な数のステップを実行する関数です。

リアルタイム コンピューティングでは、アルゴリズムが常に時間どおりに終了することを保証するために最悪の場合にどれだけの時間が必要になるかを知ることが重要であるため、最悪の場合の実行時間は特に重要になります。

平均パフォーマンスと最悪ケースのパフォーマンスは、アルゴリズム分析で最もよく使用されます。最良ケースのパフォーマンスはあまり広く見られませんが、用途はあります。たとえば、個々のタスクの最良ケースがわかっている場合は、それを使用して全体的な最悪ケース分析の精度を向上させることができます。 コンピューター科学者は、確率分析手法、特に期待値を使用して、予想される実行時間を決定します。

これらの用語は、他の文脈でも使用されます。たとえば、伝染病の最悪の場合と最良の場合の結果、電子回路要素がさらされる最悪の温度などです。指定された許容値のコンポーネントが使用される場合、デバイスは、許容値と外部条件の最悪の組み合わせでも適切に動作するように設計する必要があります。

ベストケースのパフォーマンスという用語は、コンピュータ サイエンスにおいて、最適な条件下でのアルゴリズムの動作を説明するために使用されます。たとえば、リストの単純な線形検索の場合、目的の要素がリストの最初の要素である場合にベストケースが発生します。

アルゴリズムの開発と選択は、最良のケースのパフォーマンスに基づいて行われることはめったにありません。ほとんどの学術機関や商業企業は、平均的なケースの複雑さと 最悪のケースのパフォーマンスを改善することに興味を持っています。また、有限の入力セットに対するソリューションをハードコーディングすることで、最良のケースの実行時間を実現するようにアルゴリズムを簡単に変更できるため、測定はほとんど意味をなさなくなります。^[1]

最悪ケースのパフォーマンス分析と平均ケースのパフォーマンス分析にはいくつかの類似点がありますが、実際には通常、異なるツールとアプローチが必要になります。

典型的な入力が何を意味するかを判断するのは難しく、平均的な入力は数学的に特徴付けるのが難しい特性を持っていることがよくあります (たとえば、テキストの文字列を操作するように設計されたアルゴリズムを考えてみましょう)。同様に、特定の「平均的なケース」 (おそらくアルゴリズムの一部の用途にのみ適用可能) の合理的な説明が可能な場合でも、方程式の分析がより困難になる傾向があります。^[2]

最悪ケース分析では安全な分析が行われます (最悪のケースが過小評価されることはありません) が、これほど多くの手順を実行する (現実的な) 入力が存在しない可能性があるため、過度 に悲観的になる可能性があります。

状況によっては、安全性を保証するために悲観的な分析を使用する必要がある場合があります。ただし、悲観的な分析は悲観的すぎる場合が多いため、実際の値に近づきながらも楽観的な分析 (おそらく、故障の確率が低いことがわかっている) の方がはるかに実用的なアプローチになる可能性があります。最悪のケースの分析と平均的なケースの分析の間のギャップを埋めるための学術理論における最新のアプローチの 1 つは、平滑化分析と呼ばれます。

完了するまでに通常短い時間しかかからないが、定期的にはるかに長い時間を必要とするアルゴリズムを分析する場合、償却分析を使用して、一連の操作（おそらく無限）にわたる最悪の実行時間を決定できます。この償却コストは平均コストに非常に近くなりますが、実行時間の上限は保証されています。そのため、たとえばオンライン アルゴリズムは、償却分析に基づいていることがよくあります。

最悪ケース分析は最悪ケースの複雑さと関連している。^[3]

最悪の場合のパフォーマンスが悪いアルゴリズムの多くは、平均的な場合のパフォーマンスは良好です。解決したい問題にとって、これは良いことです。つまり、関心のある特定のインスタンスが平均的であることを期待できるのです。暗号化にとって、これは非常に悪いことです。暗号化の問題の典型的なインスタンスは困難であってほしいのです。ここで、ランダム自己還元性などの方法をいくつかの特定の問題に使用して、最悪の場合が平均的な場合よりも難しくないこと、または同等に、平均的な場合が最悪の場合よりも簡単でないことを示すことができます。

一方、ハッシュ テーブルなどの一部のデータ構造では、最悪のケースの動作が非常に悪くなりますが、十分なサイズで適切に記述されたハッシュ テーブルでは、統計的に最悪のケースが発生することはありません。実行される操作の平均数は指数関数的な減少曲線に従うため、操作の実行時間は統計的に制限されます。

• 挿入ソートは、n要素のリストに適用され、すべての要素が異なり、最初はランダムな順序であると想定されます。平均すると、リストA ₁ ... A _{j の}要素の半分は要素A _{j +1}より小さく、残りの半分は大きくなります。したがって、アルゴリズムは平均して挿入される( j  + 1)^{番目の要素を、すでにソートされたサブリストの半分と比較します。つまり、} t _j = j /2 です。結果として得られる平均ケースの実行時間を計算すると、最悪のケースの実行時間と同様に、入力サイズの 2 次関数が得られます。
• クイックソートは、 n要素のリストに適用され、ここでもすべて異なるものと想定され、最初はランダムな順序になっています。この人気のソート アルゴリズムは、平均ケースのパフォーマンスが O( n  log( n )) であるため、実際に非常に高速なアルゴリズムとなっています。ただし、最悪のケースの入力では、パフォーマンスは O( n ² ) に低下します。また、「最短優先」ポリシーで実装すると、最悪のケースの空間計算量は O(log( n )) に制限されます。
• ヒープソートは、すべての要素が同じ場合、O(n) 時間がかかります。ヒープ化には O(n) 時間がかかり、その後ヒープから要素を削除すると、n 要素ごとに O(1) 時間がかかります。すべての要素が異なる必要がある場合、実行時間は O(nlog(n)) に増加します。
• ボゴソートでは、最初の反復で要素をソートする場合、O(n) の時間がかかります。各反復で、すべての要素が順序どおりかどうかがチェックされます。可能な順列は n! 個あります。バランスの取れた乱数ジェネレーターを使用すると、配列のほぼすべての順列が n! 回の反復で生成されます。コンピューターのメモリは限られているため、生成された数字は循環します。各順列に到達できない可能性があります。最悪の場合、これは O(∞) 時間、つまり無限ループにつながります。

• n個の要素を持つリストの線形検索。最悪の場合、検索ではすべての要素を 1 回ずつ訪問する必要があります。これは、検索対象の値がリストの最後の要素であるか、リストにない場合に発生します。ただし、平均的には、検索対象の値がリスト内にあり、各リスト要素が検索対象の値である可能性が等しいと仮定すると、検索ではn /2 個の要素のみが訪問されます。

• ソートアルゴリズム– さまざまなアルゴリズムのパフォーマンス分析が大量に行われる領域。
• 検索データ構造– 特定の項目を効率的に検索できるデータ構造
• 最悪の場合の回路解析
• 平滑化分析
• 区間有限要素
• ビッグオー表記