大O表示法和θ表示法的区别在于，为什么(θ)Ө-表示法适合插入排序来描述其最坏的运行时间？

Question

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)。

​

​

Answer 1

Ө的使用-表示法:

如果任何函数具有相同的上界和下界，我们可以用Ө-表示法来描述它的时间，它的上界和下界可以用单个表示法来指定。它简单地告诉了更多关于该函数的特性。

示例，

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).

Answer 2

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

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

Answer 3

插入排序时间“计算”复杂性: 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 )，这是插入排序的最佳版本：间隙插入排序。

但是如果你在寻找更快的排序算法，就会有计数排序，在最坏的情况下它有时间: O(3n)，当k=n (所有符号都是唯一的)，空格: O(n)