algorithm - アルゴリズム、上限/下限、および最良/最悪のケース

Question

アルゴリズムの場合、境界は最良/最悪のケースにどのように関連していますか? 最悪のケースは上限と同義であり、最良のケースは下限と同義ですか? または、少なくとも一方を他方から派生させることができますか? それとも、まったく関係がないのでしょうか?

Answer 1

はい、最悪の場合は上限と同義であり、最良の場合は下限と同義です。

最悪の場合のパフォーマンスは、アルゴリズム分析で最もよく使用されます。最悪の場合の分析では、良い情報であるアルゴリズムの実行時間の上限を保証します。つまり、最大数の操作が実行される実行を見つける必要があります。最良のケースの分析では、アルゴリズムの実行時間の下限を計算します。最小数の操作が実行されるケースを知る必要があります。

最後の質問に関しては、はい、平均ケースのメトリックを使用して、最悪のケースまたは最良のケースのシナリオを絞り込む/解決できます。O、Θ、Ω がそれぞれ最悪の場合、平均的な場合、最良の場合のシナリオを表し、f(n) と g(n) が 2 つの任意の関数であるとします。

1) f(n) = O(g(n)) かつ f(n) = Θ(g(n)) ==> f(n) = Ω(g(n) ) の
場合 2) f(n)の場合= Ω(g(n)) および f(n) = Θ(g(n)) ==> f(n) = O(g(n))

Answer 2

最悪の場合の分析では、アルゴリズムの実行時間の上限を計算します。最大数の操作が実行されるケースを知る必要があります。線形検索の場合、検索対象の要素 (上記のコードでは x) が配列に存在しない場合に最悪のケースが発生します。ほとんどの場合、アルゴリズムを分析するために最悪のケースの分析を行います。最悪の分析では、良い情報であるアルゴリズムの実行時間の上限を保証します。

最良のケースの分析では、アルゴリズムの実行時間の下限を計算します。最小数の操作が実行されるケースを知る必要があります。線形探索問題では、x が最初の位置にあるときに最良のケースが発生します。ベスト ケース分析は偽物です。アルゴリズムの下限を保証しても、最悪の場合、アルゴリズムの実行に何年もかかる可能性があるため、情報は提供されません。