運行時間的排序代碼

Sort(B) 
for i = 0 to (n-1) 
    x = (i+1); 
    for j = (i+2) to n 
     if B[x] > B[j] 
      x = j; 
    if x != (i+1) 
     temp = B[i+1]; 
     B[i+1] = B[x]; 
     B[x] = temp;

什麼是運行時間T（n）？問題出在內環（對於j =（i + 2）到n）內環最壞的情況是什麼？什麼是最好的情況？我認爲他們是相同的，因爲它是獨立的，但我想確定。運行時間的排序代碼

來源

2015-06-03 user3552818

無論輸入如何，內循環對於給定的外循環迭代總是具有相同的迭代次數。 –

運行時間爲O（n^2）。

每個內環需要O(n-i)時間，用於將i的值從0增加到n-1。

這讓你有時間的複雜性：

T(n) <= CONST*(n-0 + n-1 + n-2 + ... + n-(n-1)) = 
    = CONST*(1 + 2 + ... + n) = CONST*(n(n+1)/2)

最後的等式來自sum of arithmetic progression。由於n（n + 1）/ 2在O（n^2）中，所以這是時間複雜度。

來源

2015-06-03 19:11:09 amit

它不是這個例子的確切公式，因爲內循環做n-i-2。但我們當然可以刪除那2，因爲它不會改變整個圖片。這將是類似於（n *（n + 1）/ 2） - 2 * n –

@GiorgiNakeuri它不應該給出確切的公式，它是與常量的近似值，我添加了CONST *或清晰度。 – amit

謝謝。得到它了：） – user3552818

另一個答案顯示算法的運行時間是O（n^2）。我只想指出算法對我來說看起來不完全正確，因爲它無法對數組的第一個元素（在這種情況下是B [0]）進行排序。

來源

2015-06-03 19:36:29 Zlol

運行時間的排序代碼

回答

相關問題