下限と最悪のシナリオ

Question

下限が問題を解決するために必要な最小作業量であることを知っています。したがって、特定の問題については、それは最良のアルゴリズム（この問題を解決するための最も効率的なアルゴリズム）を有すると言うと、アルゴリズムYはこのアルゴリズムYから計算された下限効率が最も少ない時間であり、この問題Xを介して解くことができる時間である。それでは、最悪の場合の入力でこのアルゴリズムの下限効率を計算するのですか？ベストケース入力ではありませんか？私は下限を意味することです。したがって、最良のケースシナリオで発生する最小作業量です。ある種の選別アルゴリズムの下限を解決するための決定木アルゴリズムの問題を見るたびに、通常の単語は常に「最悪の場合は下限はBlah Blah Blah」を私を混乱させることです！誰かが私の理解を直してください:(。

Answer 1

アルゴリズムを分析するとき、それは非常に些細なシナリオを考慮して非常に有益ではなく、非常に有益ではないので、それはほとんど意味がありません。

ほとんどすべてのアルゴリズムを適応させることができる $ o（n）$ の最も重要な複雑さを持つように適応させることができることをあなた自身に納得させることができます。 -container "> $ n $ 入力インスタンスが解決策が些細なインスタンスのクラスに属しているかどうかを確認するだけで、入力のサイズです。

具体的な例を与えるために：数字の入力シーケンスかどうかをチェックするだけの場合、各ソートアルゴリズムに最適な場合は、 $ o（n）$ にすることができます。すでにソートされています。

フォーカスはしばしば最悪の場合の複雑さにあります。最悪の場合の複雑さに関してアルゴリズムを比較したいと判断したら、問題を解決できるかを尋ねることも理にかかります。

問題を解決するのに必要な時間に急激な束縛を与えることは通常不可能であるため、上限と下限を求めています。

$ O（f（n））$ の上限（ $ O（f（n））$ 最悪の場合の時間。

$ \ omega（g（n））$ の下限考えられないアルゴリズムが $ O（g（n））$ 問題を解決する時間。

明確にする：問題を解決するのに必要な時間の下限は、入力サイズ $ n $ の関数として表され、最小の量です。 span class="math-container"> $ n $ のすべてのインスタンスを解決するために必要な作業の。直感的に（正式な定義ではない）それを $ \ min_ {a \ mathcal {a}} \ max_ {i \ in \ in \ mathcal {i} _n} tとして考えることができます。 （a、i）$ ここで、 $ \ mathcal {a} $ は、問題を解決するすべての可能なアルゴリズムのセットです。 $ \ mathcal {i} _n $ は、size $ n $ 、 $ t（a、i）$ は、 $ a \ in \ in \ mathcal {a} $ で必要な時間です。="math-container"> $ i \ in \ mathcal {i} _n $ 。

代わりに念頭に置いているように思えるのは $ \ min_ {a \ mathcal {a}} \ min_ {i \ in \ mathcal {i} _n} t（ a、i）$ 。

問題の下限は、問題が解決することである「難しい」方法を確立するのに役立ちます（私たちが代わりに最も簡単なインスタンスを見れば、これはほとんど意味がありません）、そしてアルゴリズムが最適であることからどれだけ離れているかを測定します。 たとえば、マージソートは、実行時間（漸近的）が $ \ OMEGA（n \ log n）$ 下限に一致するため、ソートの問題を最適な時間に解決します。ソートの問題（比較ベースのモデル）

Answer 2

「下限」はシナリオごとに適用でき、個別に意味がありません。（どんなものの下限？）最悪のシナリオを分析したときのほとんどの場合、アルゴリズムの時間的な複雑さとして、「下限」が最悪のシナリオ（最良の場合ではなく）に適用されます。 つまり、最悪のシナリオについての時間の複雑さが説明されているので、時間の複雑さの「下限」が最悪のシナリオに適用されます。