計算和基數排序的運行時間

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次）遍歷數組一次。