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

Ө-notation 的使用：

如果任何函数的上界和下界都相同，我们可以使用Ө-notation 来描述它的时间复杂度。它的上界和下界都可以用一个符号来指定。它只是更多地说明了函数的特性。

例子 ，

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

插入排序时间“计算”复杂度：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 回答
1

插入时间的最佳情况运行时间是 Ө(n) ，最坏情况是 Ө(n^2) 准确地说。所以插入排序的运行时间是 O(n^2) 而不是 Ө(n^2)。O(n^2) 意味着算法的运行时间应该小于或等于 n^2，其中 Ө(n^2) 意味着它应该完全等于 n^2。

最坏情况下的运行时间永远不会小于 Ө(n^2)。我们使用 Ө(n^2) 因为它更准确。

于 2013-03-25T06:14:00.817 回答