如何证明计数排序O(n+K)复杂度中K为输入值域？附实例疑问

一、为什么计数排序O(n+K)中的K是输入的值域？ #

计数排序的核心逻辑依赖一个频率统计数组，这个数组的长度由输入元素的值域范围决定：

1. 遍历输入数组（O(n)时间），统计每个元素出现的次数，存储到频率数组中。
2. 遍历频率数组（O(K)时间），根据统计的次数生成排序后的结果。

这里的K就是值域对应的元素个数，即「最大值 - 最小值 + 1」（针对整数元素场景）。因为频率数组必须覆盖所有可能出现的输入值，遍历它的时间复杂度由值域大小决定，因此总时间复杂度为O(n+K)。

二、为什么K有时会等同于输入的最大值？ #

这种情况只在输入元素最小值为0的场景下出现简化表述：

• 当输入最小值是0时，值域大小为「最大值 - 0 + 1 = 最大值 + 1」，若最大值数值很大，「最大值」和「最大值+1」的量级几乎无差异，部分资料会简化称K等于最大值。
• 若输入是从0开始的连续非负整数，值域大小刚好等于最大值+1，但部分场景会直接用最大值指代K的量级，这是一种口语化的简化表述。

三、输入列表[5,7,6]的K值是多少？ #

你混淆了「值域的大小」和「最大值的数值」，正确的K是3：

• 该列表最小值为5，最大值为7，值域是5到7，包含5、6、7三个整数，因此值域大小（即K）为7-5+1=3。
• 你创建的长度为3的索引数组（0-2），这个长度就是K的数值。后续通过「索引+最小值」还原元素的操作是正确的，但把索引对应的还原值（7）当成K是错误的，K是频率数组的长度，也就是值域覆盖的元素总数。

内容的提问来源于stack exchange，提问作者Jeroum Fiveroeven