排序算法的複雜性

-1

這裏是一個排序算法，而不是一個聰明的算法。在這個版本中，當元素是非負的並且最多隻發生一次時，它可以很好地工作。我對它的時間複雜性感到困惑。它是O（n）嗎？那麼比這個符號快速排序更好嗎？謝謝。下面是代碼：排序算法的複雜性

public int[] stupidSort(int[] array){ 

// Variables 
int max = array[0]; 
int index = 0; 
int[] lastArray = new int[array.length]; 

// Find max element in input array 
for(int i = 0; i < array.length; i++){ 
    if (array[i] > max) 
    max = array[i]; 
} 

// Create a new array. In this array, element n will represent number of n's in input array 
int[] newArray = new int[max + 1]; 

for (int j = 0; j < array.length; j++) 
    newArray[array[j]]++; 

// If element is bigger than 0, it means that number occured in input. So put it in output array 
for(int k = 0; k < newArray.length; k++){ 
    if(newArray[k] > 0) 
    lastArray[index++] = k; 
} 
return lastArray; 
}

來源

2017-02-25 aladinsane7

你寫什麼counting sort，它有O（n）的複雜性確實。但是，它不能與QuickSort相比，因爲QuickSort是基於比較的算法。這2種算法屬於不同的類別（你的是一個非比較，quicksort是一種比較算法）。您的算法（計數排序）假定數組中的數字範圍是已知的，並且所有數字都是整數，而QuickSort適用於每個數字。

您可以通過排序算法0瞭解更多信息。在該鏈接中，您可以看到分爲兩類的排序算法的複雜性：比較和非比較。

EDIT

正如Paul Hankin指出複雜性不總是爲O（n）。它是O（n + k）其中k是輸入數組的最大值。下面引用是維基百科的文章中爲counting sort解釋的時間複雜度：

由於該算法只使用for循環簡單，沒有遞歸或子程序調用，這是簡單的分析。計數數組的初始化以及在計數數組上執行前綴和的第二個for循環每個迭代最多k + 1次，因此需要O（k）次。另外兩個for循環，以及輸出數組的初始化，每個都花費O（n）次。因此，整個算法的時間是這些步驟的時間總和，O（n + k）。

來源

2017-02-25 18:48:58 Thanasis

感謝您的回答和建議。 – aladinsane7

不客氣。您也可以將我的答案標記爲已接受。謝謝：）！ – Thanasis

該算法不是O（n）。 'new int [max + 1]'（以及後面的'k'循環）需要O（'max'）時間，這個時間可能比'n'任意地更差。 –

給出的算法非常類似於計數排序。而QuickSort是一種基於比較模型的排序算法。只有在最壞的情況下，QuickSort給出了O（n^2）的時間複雜度，否則就是O（nlogn）。 快速排序與它一起使用隨機化版本是樞軸隨機選擇，因此最糟糕的情況最經常以這種方式避免。

編輯：如在評論複雜paulhankin = O指出（N + K）更正：

你現在提出的代碼使用計數根據排序，也就是數排序和你的代碼的時間複雜度是O（n + k）。但是你必須認識到的是，這個算法取決於輸入的範圍，而範圍可以是任何東西。此外，該算法不是InPlace而是穩定。在許多情況下，您想要排序的數據不僅是整數，而且數據可以是任何具有需要藉助密鑰進行排序的密鑰的數據。如果穩定算法沒有使用比在這種情況下排序可能有問題。

以防萬一，如果有人不知道：

原地算法：是對在其中需要額外的空間是不依賴於給定的輸入。

穩定算法：例如，如果在排序之前數據集中有兩個5，那麼在排序之前，排序之前排在第一位的5比排在第一位的優先。

編輯：（關於aladinsane7的評論）：是的countSort正式版本還沒有處理這方面。如果你看一下CountSort就好了。其時間複雜度爲O（n + k）。其中K說明了數據的範圍，而n是剩餘算法的複雜度。

來源

2017-02-25 18:54:37

謝謝。如果我們希望它適用於相同數字出現多次的情況，我們需要另一個循環以「newArray」運行。那麼它的複雜性會是什麼？有任何想法嗎？ – aladinsane7

我對我的回答做了相關編輯。這將回答您的查詢。 –

在你的回答中，你說時間複雜度毫無疑問是O（n），但後來你會說它是O（n + k）。後者是正確的，前者是不正確的。 –

排序算法的複雜性

回答

相關問題