計算排序算法的操作次數

這是我的任務問題：用示例快速排序，合併排序和堆排序來解釋。通過這些排序方法中的每一種，進一步統計操作次數。計算排序算法的操作次數

我不明白我在「計算操作次數」的情況下到底需要回答什麼？

我發現coremen書第2章的東西，他們已經解釋插入排序，通過計算每個語句的運行時間的算法的運行時間....

我必須用同樣的方式呢？

2010-09-05 Tony

你需要確定它們的複雜性（無論是最壞情況還是平均情況） – 2010-09-05 03:05:33

要計算操作的數量也被稱爲對analyze the algorithm complexity。這個想法是粗略的想法，在最大的情況下需要多少操作才能在大小爲N的輸入上執行該算法，從而爲您提供該算法所需的計算資源的上界。並且由於每個操作本身（例如乘法或比較）都是有限操作並且需要確定性時間（即使它可能在不同的機器上有所不同），以便了解算法的好壞，特別是與其他算法，所有你需要知道的是大量的操作。

下面是一個氣泡排序的例子。假設你有兩個數字的數組。爲了排序它，你需要比較兩個數字並且可能交換它們。由於比較和交換是單一操作，因此執行它們的確切時間很少，而且本身並不重要。因此，可以說N = 2時，操作次數爲O（N）= 1。然而，對於三個數字，在最壞的情況下需要三個操作 - 比較第一個和第二個操作並且可能交換它們，然後比較第二個和第三個操作並交換它們，然後再次比較第一個和第二個操作。當你繼續推廣氣泡排序時，你會發現可能要排序N個數字，你需要對第一個數字進行N次操作，對第二個數字執行N次操作，等等。換句話說，對於足夠大的N，可以將O（N）= N +（N-1）+ ... + 2 + 1 = N *（N-1）/ 2簡化爲O（N）= N^2。

當然，你可以在網上作弊並找出三種排序算法中的每一種算法的O（N）數字，但我會敦促你花時間並嘗試自己拿出那個數字第一。即使你弄錯了，將你的估計和你如何得到它以及估計它們的複雜性的實際方法進行比較，將有助於你更好地理解分析將來編寫的特定軟件的複雜性的過程。

來源

2010-09-05 03:23:25

這叫做big O notation。

這page顯示了最常見的排序算法和他們通過比較大O.表示

計算複雜（最差，平均和幾種典型的測試用例比較的最佳數量，見下面）。通常，比較/操作的良好的平均數目是O（n日誌 n）和壞是O（n^2）

從http://www.softpanorama.org/Algorithms/sorting.shtml

來源

2010-09-05 03:07:47

@Franci @Zafer @ Mitch-感謝你們所有人。 – Tony 2010-09-05 04:51:56

我認爲這個任務是給你一個想法，算法的複雜性是如何計算的。例如冒泡排序算法的複雜度爲O（n^2）。

// Bubble sort method. 
// ref: [http://www.metalshell.com/source_code/105/Bubble_Sort.html][1] 
for(x = 0; x < ARRAY_SIZE; x++) 
    for(y = 0; y < ARRAY_SIZE-1; y++) 
    if(iarray[y] > iarray[y+1]) { 
    holder = iarray[y+1]; 
    iarray[y+1] = iarray[y]; 
    iarray[y] = holder; 
    }

正如您在上面看到的，使用了兩個循環來對數組進行排序。讓ARRAY_SIZE爲n。那麼操作次數是n *（n-1）。這使得由O（N^2）表示的n^2-n。這是大O符號。我們只取最具指數，最高增長率的n。如果它是2n^2 + 2n，這仍然是O（N^2），因爲在計算複雜度時也省略了常量。關於Big O Notation的維基百科文章非常有用（正如Leniel在他的文章中提到的那樣）。

這是你的功課，所以我沒有深入你提到的算法的細節。但是你需要像這樣做數學。但我認爲你被問到的是實際的操作次數。所以，對於上面的例子，如果ARRAY_SIZE是10，答案得到10 * 9 = 90。要查看您的示例代碼中需要使用相同數組的差異。

來源

2010-09-05 03:56:35 Zafer

計算排序算法的操作次數

回答

相關問題