计数排序时间复杂度为何是O(n+k)而非O(2n)？

首先得指出你贴的这段示例代码存在几个明显错误，这可能是你产生误解的原因之一：

• 第一个循环里arr[i+1]++逻辑错误，应该是arr[nums[i]]++，这样才是统计每个数值的出现频率；
• 第二个循环里nums[i]=arr[i]完全不对，正确做法是维护一个指针，把当前数值按频率依次填充到nums的对应位置，而非直接给nums[i]赋值。

回到你的核心疑问：为什么计数排序的时间复杂度是O(n+k)而非O(n)？

原因在于，计数排序的第二阶段不能只看while循环的总执行次数，外层遍历取值范围的过程必须算进去：

• 外层for循环会遍历从最小值到最大值的所有k个可能取值，哪怕某个取值在数组里完全没出现（频率为0），这个循环也会执行一次判断；
• 内层while循环的总执行次数确实是n，因为每个元素都会被重新填充一次。

所以第二阶段的总时间复杂度是O(k + n)，加上第一阶段统计频率的O(n)，整体就是O(n + k)。

举个极端例子就懂了：假设数组只有10个元素（n=10），但元素取值范围是1到100000（k=100000）。这时候第二阶段的外层for循环要跑100000次，而while循环总共只跑10次，显然这部分时间主要由k决定，总复杂度就是O(10+100000)=O(k)，远大于O(n)。

只有当k远小于n时，O(n+k)才会等价于O(n)，但计数排序的时间复杂度必须考虑k这个变量——它在某些场景下会成为主导因素。

内容的提问来源于stack exchange，提问作者Kaito Ace