大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符號和θ符號之間的區別，爲什麼（θ）符號適合插入排序來描述其最壞情況下的運行時間？

回答

相關問題