计数排序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？

回答

相关问题