時間計算複雜度？

-3

我有這個排序代碼，下面是冒泡排序，但我認爲這個代碼不完全是O（N^2）。我想知道下面這段代碼在大O方面的時間計算複雜度是多少。我猜這是O（N.logN）。時間計算複雜度？

代碼只是作爲例子給出，並沒有聲稱它是可編譯的。

for(i = 0; i < n-1; i++) 
{ 
    for(j = 0; j < n-i-1; j++) 
    { 
     if (a[j+1] < a[j]) 
     { 
      temp = a[j]; 
      a[j] = a[j+1]; 
      a[j+1] = temp; 
     } 
    } 
}

來源

2012-02-02 goldenmean

什麼「代碼在下面」？ – 2012-02-02 10:02:19

@PaulR Blooper糾正 - 現在發佈代碼。 – goldenmean 2012-02-04 14:51:33

我想這是O（N.logN）。

爲什麼猜測？看看實際發生了什麼...

第一次雖然外環，i == 0.這意味着j將範圍從0到n-1。

第二次通過，i == 1，所以j的範圍從0到n-2。

儘管第三次，i == 2，所以j的範圍從0到n-3。

...

最後一次通過，我== n-1個，所以Ĵ範圍從0到0

所以，操作的總數目爲n-1 + n-2個+ n-3 + ... + 0.

什麼是總和Σi，i = 0..n-1？現在將其轉換爲大O界限。

來源

2012-02-04 15:25:11 Caleb

Caleb的權利。它可能「感覺」小於O（n^2），因爲內循環隨着外循環的每次迭代而變短，並且確實比內循環每次變爲「n」時更快。然而，它並沒有改變整體事實，即工作量與n成指數增長。 – 2012-02-04 16:57:03

@Caleb感謝數學。是的，總的迭代次數似乎是N（N-1）/ 2，所以我看它仍然是O（N^2）。 N.logN（迭代，非遞歸）算法是什麼樣的。當我們進行二分搜索時（在一個有序數組上），爲什麼當我們實際去N - > N/2 - > N/4等時，它被稱爲logN。將數組分成一半進行搜索？人們總是說二進制搜索==> logN，但我還沒有碰到它背後的數學？ – goldenmean 2012-02-04 18:11:23

@goldenmean在二進制搜索中，您將每次搜索的東西數除以2。這意味着需要log2（n）步驟才能找到任何元素。嘗試一下：如果n = 8，則需要3個步驟。如果n = 32,5個步驟。 – Caleb 2012-02-04 19:06:00

時間計算複雜度？

回答

相關問題