在计数排序中，我们知道O(n+k(是时间强制性，其中'n'是元素的数量，'k'是给定的元素范围，例如1-100。现在看看下面的计数排序代码：
void counting_sort(vector<int> & nums){
//given nums[i] is between 1 and 5
int arr[6];
for (int i=0;i<nums.size();i++){
arr[i+1]++;
}
// we have basically stored the frequency of values now in arr with O(n) time complexity
for (int i=0;i<=5;i++){ // 5 here is just for example, in code it should be the largest value in nums array
while (arr[i]>0){nums[i]=arr[i]; arr[i]--;}
}
//now we have stored the values in the sorted order in O(k) time complexity
//total time complexity: O(n+k)
return;
}
现在，我的问题是，既然我们必须用while循环迭代第二个for循环中的所有值，那么这个循环的时间复杂度不应该是O(n(吗？因为我们迭代所有元素的数量，而不管for循环只针对1到k的值(而循环则迭代数字的频率(。
因此，计数排序的时间复杂度不应该是O(n+n(=O(2*n(=0(n(而不是O(n+c(吗？(由于while循环将运行时间增加到n个元素，因此该范围毫无用处(
您生成两个不同的循环，第一个循环在元素(n(上，第二个循环在范围(k(上
n和k可能不同，所以你必须把它们看作两个不同的变量。
所以时间复杂性是：
O(n(+O(k(=O(n+k(
只有当k等于n或更小时，复杂性才会是：
O(n(+O(n
如果k大于n，则复杂度为：
O(n(+O(k(=O(k
我们不知道哪个更大，所以我们保留了两个变量分开的
O(n(+O(k(=O(n+k(