计算和基数排序的运行时间

Question

我知道计数和基数排序通常被认为是运行在O（n）时间，我相信我明白了为什么。然而，我在一项任务中被问到，要解释为什么这些排序可能不一定在O（n）时间排序一个明确的正整数列表。我无法想出任何理由。

任何帮助表示赞赏！

Answer 1

要说计数或基数排序是O（n）实际上是不正确的。

Counting sort是O（n + k）其中k是阵列中任何元素的最大值。

原因是你必须遍历整个列表来填充计数（O（n）），然后遍历计数（O（k））。

Radix sort是O（mn）其中m是数字的最大位数。

原因是你必须为每个数位（O（n）m次）遍历数组一次。