Big Theta Notationバブルソートを計算する

Question

バブルソートのためのシータ記号を計算しようとしていますが、私は固まっています。この手順（擬似コード）を考える：

procedure BUBBLE_SORT(A,n) { 
    array A(1 to n) 
    for (int i = 1; i <= n; i++) { 
     for(int j = 1; j <= n-1; j++) { 
      if(A[j] > A[j+1] { 
       //swap(A(j), A(j+1)) 
      } 
     } 
    } 
} 

私は最悪のケースのように、シグマの表記との時間を実行して取得することができた：

（N^2 - N）/ 2

ベスト私は自分の本を辿り、これをやりました：

p（n）=（n^2 - n）/ 2とすると、p（n）=Θ（n^2）となります。これを証明するために、我々は表示されているいくつかの定数C1のため、C2とN0：

C1N^2 < =（N^2/2）+（N/2）< = C2N^2

によって両側を割ますN^2、我々が得る：

C1 < =（1/2）+（1/2N）< = C2

私は失われてしまったところです。この本では、著者がいくつかの番号を選び、それらを差し込んで「p（n）=Θ（n^2）」と答えた。

プラグインする番号を知る方法は？任意の数字だけを差し込むことはできますか？そしてそれらの数が不等式に適合すれば、それはアルゴリズムがΘ（n^2）であるとすぐに言えるのでしょうか？

ありがとうございました！

Answer 1

私が従う一般的なアプローチは、最初に標準の複雑さの値をチェックすることです。 like 2^(2^n) > n! > 4^n > 2^n > n^2 > nlogn > log(n!) > n > sqrt(n) > (logn)^2 > logn > loglogn > 1

このようにしてプラグインn^2これで満足すればそれ以下の値を考慮してください。あなたはきつい縛りを得ることができるこの方法。そうでなければ、より高い値に対しては満足します。これは多くの場合に役立ちます。

Answer 2

これは漸近的な動作に関することです。

私たちはゲームをすることについて考えることができます：あなたの目標は、一定の境界が保持されていることを証明することです。ゲームは次のようになります：まず、定数C1とC2を選択します。それから私は任意のnを選ぶようになる。私が不平等に違反するようにこれを行うことができれば、あなたは負けます（縛りは保持されません）。あなたが選択したC1とC2を変更できなくなったとしても、私はこれを行うことができません。

それでは問題の式を見てみましょう：

C1 < =（1/2）+（1/2N）< = C2

nは、それが表す端の整数（なので配列内の要素の数）の場合、最も小さい値の一番小さい値はn = 1です。

（1/2）+（1/2）=

1よしが、今それがスタートだ：さんがでていることに置き換えてみましょう。私がnを大きくするとどうなるか見てみましょう... nは分母にしか現れません。だから私はそれを任意のものにすることであなたの限界を台無しにすることはできません。あなたの最悪の場合は、実際には小の値はnです。 nの値が大きいほど、製品の2番目の部分が小さくなり、最終的には消えます。制限n->infのために我々が得る：

LIM N-> infファイル（1/2）+（1/2N）

（1/2）+ LIM N-> INF（1/2N）=（1/2）+ 0 = 1/2

それでは、それを教えてくれることで、式はで線形であるので、私は選択nのいずれかの値、結果の値は、常に（1までの範囲の1/2であろうnこれらの2つのサンプルは、それを示すには十分であり、より複雑な方程式では、境界を確立するにはもう少し作業が必要です）。

この知識があれば、決して勝てない方法でC1とC2を選ぶことができますか？

Answer 3

は、我々はすべてのn >= 1ためC1と以下が成り立つようにC2を見つけることに興味がある：

は C1 = 1/2のための良い選択（それよりも小さい任意の厳密に正の値は例えば、また C1 = 0.1有効です

C1 <= (1/2) + (1/2n) <= C2

）。

C2 = 1（ただし、それ以上の値も有効です）には適しています。値C2 = 1は、1/2 + 1/2nの式がnになるほど小さくなるので、最大値はn = 1です。

---

最後の注意：それはn >= 1不等式が常に保持するために、いくつかの定数C1とC2があることが上に示しました。もっと便利な場合は、nの値に焦点を当てることができました（1の代わりに、たとえば）。重要なのは、とC2という定数があるため、nが十分に大きいときに両方の不等式が成り立つということです。