算法的運行時間（大O））

爲此算法計算運行時間嗎？算法的運行時間（大O））

       Cost  No Of Times 

for(j=1;j<=n-1;j++){   c1  n(loop will run for n-1 times +1 for failed cond    

    for(i=0;i<=n-2;i++){  c2  n*(n-1) (n-1 from outer loop and n for inner 

     if(a[i]>a[i+1]){  c3  (n-1)*(n-1) 

      Swap    c4  (n-1)*(n-1) {in worst case } 
     } 
    }

在最壞的情況下 T（N）= C1 * N + C2 *（N-1）N + C3（N-1）（N-1）+ C4 *（正1）（N-1） 這是O（n^2）

在最好的情況：

T（N）= C1 * N + C2 *（N-1）ñ + c3（n-1）（n-1） 這是O（n^2）。

但實際上在最好的情況下氣泡排序具有時間複雜度O（n）。 任何人都可以解釋嗎？

來源

2013-06-29 Ravi Bisla

是的，其結果是'O（n^2）'這是您在這裏做的冒泡排序的代價......您可以通過使用搜索算法的名稱並進入第一個結果。 http://en.wikipedia.org/wiki/Bubble_sort –

我已檢查，但我有一個懷疑，得出這一點，這就是爲什麼我張貼。 –

Bubble Sort在最佳情況下具有O（n）時間複雜度，因爲可以將已排序的列表傳遞給它。

您必須檢查第二個嵌套循環後是否進行了任何交換。如果沒有交換完成，列表將被排序並且不需要繼續，因此您可以打破循環。

對於已經排序的列表，在這種情況下，您將重複遍歷所有n個元素。

來源

2013-06-29 13:28:49

您的用於實現冒泡排序算法中是正確的，但效率不高，

// n是elments總數

do{ 

    swp = false // swp checks whether or not any variable has been swapped 
         in the inner loop 

     for(i=0;i<=n-2;i++){ 

        if(a[i]>a[i+1]) 

        { 
         swap(a[i],a[i+1]) 

         sw = true 
        } 
     n = n-1    
    }while(sw == true && n>0)

SWP是用於檢查是否存在已在任何交換的可變內部循環或不，
如果沒有任何交換這意味着我們的數組排序。

的冒泡排序最好的情況是，當元素上以升序已經排序（在這種情況下）
爲其內環只運行一次，但如果條件（在內環）是永不滿足和swp仍然是假的，因此我們在一次迭代之後退出外部循環，這給出了冒泡排序O（n）的複雜性。

來源

2013-06-29 14:45:02 RYO

你可以計算的迭代次數使用（什麼是循環內是無關緊要的，因爲它的固定時間）西格瑪符號：

enter image description here

冒泡排序有最好的情況下運行時間實際上是一個增強版這種排序算法。

在第一次解析（外循環）期間，如果沒有執行交換，那是數組排序的決定性信息，並且它是毫無意義的以涵蓋所有情況。

因此，外循環將重複一次，並且該內環將迭代Ñ倍：即整體==>爲O（n）是N + 1次迭代。

來源

2014-05-11 06:11:28

算法的運行時間（大O））

回答

相關問題