1

We use Ө-notation to write worst case running time of insertion sort. But I’m not able to relate properties of Ө-notation with insertion sort, why Ө-notation is suitable to insertion sort. How does the insertion sort function f(n), lies between the c1*n^2 and c2*n^2 for all n>=n0.

挿入ソートの実行時間は、Ө（n ^ 2）であるため、上限O（n ^ 2）と下限Ω（n ^ 2）があります。挿入ソートの下限がΩ（n ^ 2）なのかΩ（n）なのか混乱しています。

ここに画像の説明を入力してください

4

3 に答える 3

4

Ө表記の使用：

関数の上限と下限が同じである場合は、θ表記を使用して時間計算量を記述できます。上限と下限の両方を単一の表記で指定できます。それは単に関数の特徴についてもっと教えてくれます。

例 、

suppose we have a function , 
                  f(n) = 4logn + loglogn  
             we can write this function as 
                  f(n) = Ө(logn)
             Because its upper bound and lower bound
are O(logn) and  Ω(logn) repectively, which are same 
so it is legal to write this function as , 
                  f(n)=  Ө(logn)

証拠：

     **Finding upper bound :**

 f(n) = 4logn+loglogn


    For all sufficience value of n>=2

        4logn <= 4 logn   
        loglogn <= logn 

    Thus , 

     f(n) = 4logn+loglogn <= 4logn+logn
                          <= 5logn
                           = O(logn)       // where c1 can be 5 and n0 =2
**Finding lower bound :**

   f(n) = 4logn+loglogn

   For all sufficience value of n>=2

      f(n) = 4logn+loglogn >= logn
    Thus,              f(n) =  Ω(logn)   // where c2 can be 1 and n0=2


  so , 
                        f(n) = Ɵ(logn)

ここに画像の説明を入力してください

同様に、挿入ソートの場合： 

If running time of insertion sort is described by simple function f(n).
In particular , if f(n) = 2n^2+n+1 then 

Finding upper bound:
      for all sufficient large value of n>=1
                         2n^2<=2n^2   ------------------- (1)
                           n <=n^2    --------------------(2)
                           1 <=n^2    --------------------(3)
        adding eq 1,2 and 3, we get.
                     2n^2+n+1<= 2n^2+n^2+n^2
        that is 
                         f(n)<= 4n^2
                         f(n) = O(n^2)  where c=4 and n0=1 

Finding lower bound:
       for all sufficient large value of n>=1
                           2n^2+n^2+1 >= 2n^2
         that is , 
                                f(n) >= 2n^2
                                f(n) = Ω(n^2) where c=2 and n0=1     
      because upper bound and lower bound are same,
                                f(n) = Ө(n^2)


   if f(n)= 2n^2+n+1 then, c1*g(n) and c2*g(n) are presented by diagram:

ここに画像の説明を入力してください

最悪の場合、挿入ソートの上限と下限はO（n ^ 2）とΩ（n ^ 2）であるため、最悪の場合、挿入ソートの実行をӨ（n ^ 2））と書くことが合法です。

最良の場合、それはӨ（n）になります。

于 2013-04-29T15:54:34.153 に答える
1

挿入時間の最良の実行時間はӨ（n）であり、最悪の場合は正確にはӨ（n ^ 2）です。したがって、挿入ソートの実行時間は、Ө（n ^ 2）ではなくO（n ^ 2）です。O（n ^ 2）は、アルゴリズムの実行時間がn ^ 2以下であることを意味しますが、Ө（n ^ 2）は、n^2と正確に等しくなければならないことを意味します。

最悪の場合の実行時間は、Ө（n ^ 2）より短くなることはありません。より正確であるため、Ө（n ^ 2）を使用します。

于 2013-03-25T06:14:00.817 に答える
1

挿入ソート時間「計算」の複雑さ：O（n ^ 2）、Ω（n）

O(SUM{1..n}) = O(1/2 n(n+1)) = O(1/2 n^2 + 1/2 n)) ~ O(n^2)

Ө(SUM{1..(n/2)}) = Ө(1/8 n(n+2)) = Ө(1/8 n^2 + 1/4 n) ~ Ө(n^2)

これは、ギャップ付き挿入ソートがO（n log n）であることを示す論文であり、挿入ソートの最適なバージョンです。ギャップ付き挿入ソート

しかし、より高速な並べ替えアルゴリズムを探している場合は、k = n（すべての記号が一意）の最悪の場合に時間：O（3n）、スペース：O（n）を持つカウント並べ替えがあります。

于 2013-03-25T06:50:46.687 に答える