使用預分類及其效率的通用算法

Question

以下語句是正確的還是錯誤的？

通用算法，利用預先分類的絕不能有 最壞情況的效率比O（nlogn）更好

我相信它是真實的。因爲這個大O是O（nlogn）

Answer 1

如果後面的階段不會比O(n log n)花費更多的時間，那麼聲明爲真。此外，如果還有一些其他特殊用途的排序算法，如基數排序，計數排序，桶排序，Pancake排序，它們比基於比較的排序算法（O(nlogn)）高效（通常爲線性時間）。

Answer 2

該聲明的含義是，諸如基數排序的非比較線性排序（時間複雜度O（n））不能使用預分類。儘管基數排序的操作數量不受presorting影響，但由於預分類數據而導致的順序寫入操作的緩存局部性將提高性能。