sorting - 计数和基数排序的运行时间

Question

我知道计数和基数排序通常被认为在 O(n) 时间内运行，我相信我明白为什么。然而，我在作业中被要求解释为什么这些排序不一定在 O(n) 时间内对不同的正整数列表进行排序。我想不出任何理由。

任何帮助表示赞赏！

Answer 1

说计数或基数排序是 O(n) 实际上是不正确的。

计数排序是 O(n+k)，其中 k 是数组中任何元素的最大值。

原因是您必须逐步遍历整个列表以填充计数 (O(n))，然后逐步遍历计数 (O(k))。

基数排序是 O(mn)，其中 m 是数字的最大位数。

原因是您必须为每个数字单步遍历数组一次（O(n) m 次）。