最悪の場合の分析は漸近的な境界と等しくないですか

Question

これが本当である理由を誰かに説明することはできますか？教授がこれが彼の講義だと言われたと聞きました

Answer 1

2つの概念は直交しています。

最悪の場合の漸近線を持つことができます。 f(n)が入力nで与えられたアルゴリズムによって取られた最悪の場合の時間を表す場合、例えば、 f(n) = O(n^3)または最悪の場合の時間複雑度の他の漸近上限。は、nの均一分布型（ランダム）入力で同じアルゴリズムが使用された平均時間です。g(n)は、g(n) = O(n^2 log n)とすることができます。

h(n) = O(n)ここで、h(n)は、サイズがn（特に並べ替えアルゴリズムのほとんどの並べ替えられたシーケンス）の特に分布ランダム入力で同じアルゴリズムがとる平均時間です。

漸近表記は「尺度」です。

時には、漸近の下限（最悪のケースの複雑さ）を述べたいと思うことがあります。次に、f(n) = Omega(n^2)と書くと、最悪の場合、複雑さは以上、n^2となります。大きなオメガの表記法は、ビッグオーバーの反対であるf = Omega(g)g = O(f)の場合にのみ表示されます。

Answer 2

漸近的な境界は、操作の回数が無限になると予想される動作です。数学的には、nが無限大になるとlimだけである。しかし、最悪の場合の動作は有限数の操作に適用されます。

Answer 3

たとえば、quicksortとします。クイックソートの各連続した再帰呼び出しnは 'に

T（N）= O（N）+ 2 T [（N-1）/ 2]

の実行時の複雑さT（n）を有していますソートされていない入力リストが、各呼び出しでサイズ（n-1）/ 2の2つの等しいサブリストに分割されている場合、「最良のケース」となります。この場合、T（n）を解くとO（n log n）となる。パーティションは完璧ではないと、2つのサブリストは、同じサイズnのすなわち

T（N）= O（N）+ T（K）+ T（N - 1 - k）がない場合、

k = 1であってもO（n log n）を得ることができます。これは、k> 0である限り、入力リストを処理している間にquicksortの再帰呼び出しの数が指数関数的に増加しているためです。

しかし、 '最悪の場合' に入力リストの何分割が行われない、すなわち：

T（N）= O（N）+ T（0）+ T（N - 1）= O （n-1）+ T（n-1）+ T（n-2）...となる。

ソートされたリストの最初の要素をピボット要素として取ります。

ここで、T（0）は結果のサブリストの1つがゼロであることを意味し、したがって計算時間はかかりません（サブリストには要素がないため）。残りの負荷T（n-1）はすべて第2のサブリストに必要である。この場合、O（n²）を得る。

アルゴリズムに最悪のシナリオがない場合は、O [f（n）]だけでなくo [f（n）]（Big-O vs. little-o notation）でもあります。