運行時間分析修改泡沫排序

我正在做一個家庭作業的任務，其中我需要找到一個修改後的氣泡排序數據集的大小爲n作出的比較次數。數據集被認爲是一個已排序的列表，其中所述第一和最後一個元素進行交換，例如：52341.下面是該算法的僞代碼：運行時間分析修改泡沫排序

i <- n-1; new_i <- i 
while i > 0 do 
    for j=1 to i do 
     if A[j] > A[j+1] do 
      A[j] <=> A[j+1] 
      new_i <- j 
     endif 
    endfor 
    i <- new_i - 1; new_i <- i 
endwhile

A爲所述數據集和< =>是一個交換。

我想找到一種方法來表示這種算法，並將求和簡化爲給定類型的數據集上的比較量的表達式。

沒有給出答案，任何人都可以把我推向正確的方向嗎？

來源

2012-09-21 dr7164

拿出一張紙，「執行」通過對你提供的數據的步驟，算法的一步，將真正幫助。 – KCH

在您的Bubblesort實現中，比較次數完全由輸入大小決定，即輸入列表中元素的順序無關緊要。

如果你可以證明這一點（這不是很難），那麼可以計算大小爲N的輸入列表的比較次數。因爲我們已經證明次序並不重要，所以這仍然是相當公平的容易：

我們有兩個循環，外部while循環和內部for循環。外循環從n到1（或n-1到0，但肯定不是從n-1到1，如代碼所示），即我們有N次迭代。內部循環從1到i。因此，我們在外循環的第一次迭代中N次比較，在第二次中N-1次，在第N次中N-2次，...，N-N中有0次比較。

我認爲你自己來了這麼遠。否則，無論如何你都會被搞砸。

什麼你的老師現在要看到的是，你知道下面的公式，即所謂的「GaußscheSummenformel」，也被稱爲「高斯總和」：

N +（N-1）+（N- 2）+ ... +（NN + 1）+（NN）= N^2/2 + N/2

所以你應該在這裏做的是：

秀比較的數量只有取決於輸入的大小
顯示比較數等於N +（N-1）+（N-2）+ ... +（N-N + 1）+（NN）
提及這與N^2/2 + N/2，指高斯先生。

;-)

來源

2012-09-21 11:18:06 Philip

運行時間分析修改泡沫排序

回答

相關問題