大O符号和θ符号之间的区别，为什么（θ）符号适合插入排序来描述其最坏情况下的运行时间？

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.大O符号和θ符号之间的区别，为什么（θ）符号适合插入排序来描述其最坏情况下的运行时间？

运行插入排序的时间作为Ө（N^2）意味着它具有上限为O（n^2）和下限Ω（N^2）。我很困惑插入排序下界是Ω（n^2）还是Ω（n）。

enter image description here

来源

2013-03-25 siddstuff

我投票决定将此视为“不是真正的问题”，这是SE总结为的一个条件：“很难说出这里提出的问题。这个问题不明确，模糊，不完整，过于宽泛或修辞，并且不能按照目前的形式合理地回答。“具体而言，第二段充满了错误信息，整个事情是一个问题，而不是一个问题。 – 2013-03-25 06:15:08

我的问题是，“为什么我们使用Ө符号进行插入排序？”我想这可以回答。我在这个问题上写下了所有的疑问。我想这些怀疑使人怀疑。 – siddstuff 2013-03-25 06:33:02

考虑将编辑移动到新答案并接受答案（是的，您可以回答自己的问题并接受答案）。这样，你们都可以起来投票并将问题标记为已回答。 – Shahbaz 2013-04-29 15:47:40

使用Ө表示法：

如果任何函数具有相同的两个上限和下限，我们可以使用Ө表示法complexity.Both它的上限和下限可与单数指定来形容它的时间。它只是告诉更多关于功能的特征。

实施例，

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)

enter image description here

类似地，在插入排序的情况下：

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:

enter image description here

在最坏的情况下，插入排序上界和下界是为O（n^2）和Ω（N^2），因此在最坏的情况下是合法的将插入排序的运行写为Ө（n^2））

在最好的情况下，它将是Ө（n）。

来源

2013-04-29 15:54:34 siddstuff

在这里，取这个+1 – Shahbaz 2013-04-29 15:55:03

运行的插入时间的时间最好的情况是Ө（n）和最坏的情况是Ө（N^2）要精确。所以插入排序的运行时间是O（n^2）而不是Ө（n^2）。 O（n^2）表示算法的运行时间应小于或等于n^2，其中as（n^2）表示它应该完全等于n^2。

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

来源

2013-03-25 06:14:00 banarun

如果f（n）属于Ө（g（n）），我们将它写为f（n）=Ө（g和属性表明存在常数c1，c2和n0，使得0 <= c1 * g（n）<= f（n）<= c2 * g（n）对于所有n> n0，它并不意味着f （n）应该完全等于c1 * g（n）或c2 * g（n） – siddstuff 2013-03-25 06:24:32

插入排序时间 “计算” 复杂度：为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）的，最佳的插入排序的版本：Gapped Insertion Sort

但是，如果你正在寻找更快的排序算法，有Counting Sort具有时间：在其最坏情况下O（3N）当K = N（所有的符号都是唯一的），空间：为O（n ）

来源

2013-03-25 06:50:46

他没有寻找额外的算法。 OP的问题很明确，并且与大Ө表示法有关，所以请保留在主题上 – Alexander 2013-03-25 09:36:13

@Alexander我回答了他的问题，其他信息是额外的，它们与该主题有关。 – 2013-03-25 11:46:22

大O符号和θ符号之间的区别，为什么（θ）符号适合插入排序来描述其最坏情况下的运行时间？

回答

相关问题