計數排序O（n + k）時間複雜度是什麼k？

計數排序最差，最佳和平均時間複雜度爲O(n+k)，其中n是要排序的元素數。 究竟k是什麼？我看到了不同的定義：最大元素，最大元素和最小元素之間的差異，等等。計數排序O（n + k）時間複雜度是什麼k？

鑑於陣列arr1 [1, 3, 5, 9, 12, 7 ]和arr2 [1,2,3,2,1,2,4,1,3,2] 是什麼k爲arr1和arr2？
是真的，這是愚蠢的與計數排序排序arr1因爲 n < k（元素的值從一個範圍比元件的數目來排序更寬？

2017-08-03 Code Complete

我不認爲有「等等」。 –

你大概的意思是「當n k'」。 –

這取決於你如何編碼它。您可能需要查看算法或查看時間複雜性的基礎知識，因爲這可以讓您很容易地自己弄清楚這一點。這本質上是[如何找到算法的時間複雜度]的副本（https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm）。 – Dukeling

k是鍵的範圍，即陣列槽的數量需要以涵蓋所有可能的值。因此，在數字，Max-Min+1的情況。當然，這是假定你不分配Min第一槽和Max最後浪費空間。

它是approp當k不超過n的小倍數時，讓n.k使用計數排序，因爲在這種情況下，n.k可以打敗n.log n。

來源

2017-08-03 16:20:18

非常感謝！我可以問「所需的陣列插槽的數量，以涵蓋所有可能的值，因此在數字的情況下，最大 - 最小+ 1」意味着3個元素的陣列[3,20,57] k = 3（我們有3個可能的值，所以只有3個「陣列插槽」）或k = 55（57 - 3 + 1）？附：我明白k >> n，所以我更喜歡基數排序，而不是使用計數排序... –

@CodeComplete：你也可以有'k

k是在陣列的最大可能值，假定有長度爲5，其中每個編號爲0到9之間的整數的數組，在這個例子中k等於9

來源

2017-08-03 16:24:01 Farnabaz

感謝您分享知識！我的答案是否正確：對於3個元素的數組[3,20,57] k = 57（「k是數組中的最大可能值」）？對？ –

@ code-complete是的，在你的例子中k = 57 – Farnabaz

前K計數的陣列被歸零。然後讀取數組中的n個元素，並根據n個元素的值增加k個元素的元素。在計數排序的輸出過程中，讀取k個數的數組，並寫入n個元素的數組。因此，有k個寫入（對計數爲零），n個讀取，然後k個讀取和n個寫入，總共2n + 2k個操作，但大O忽略常數2，因此時間複雜度爲O（n + k）。

來源

2017-08-04 10:05:28 rcgldr

如果我們說計數排序時間複雜度是O（n + k），那麼n是所有要排序的元素的數量，k是DISTINCT元素？例如對於數組[3，5，7，5，1，5] n = 6和k = 4？ –

@CodeComplete - 通常k是數字的範圍，最大值+ 1 - 最小值。計數陣列的大小是k。對於[3 5 7 5 1 5]，k將是7（最大值7 + 1 - min值爲1）。 – rcgldr

計數排序O（n + k）時間複雜度是什麼k？

回答

相關問題