當比較函數不是O（1）時，排序alg的時間複雜度是多少？

Question

正如我所知，當比較函數爲O(1)時，有效的排序alg時間複雜度爲O(N*log(N))。

如果比較函數不是O(1)（即O(M)），那麼時間複雜度是多少？

是O(N*log(N*M))還是O(N*M*log(N))？

感謝

Answer 1

如果每個比較需要O（M）時間 - 與O（1）時間相反，那麼整個排序需要花費M倍的時間完成 - O（ M * N log N）。這是假設M隨N增長並且不是恆定的。常量通常從大哦表示法（O（constant）== O（1））中刪除，因此這種情況下的複雜性將保持不變。這也假設你的O（Y）排序算法按O（Y）的順序進行比較，就像大多數排序算法一樣。

Answer 2

在efficent排序ALG我們(N)項目，每個項目 我們O(LOG N)比較。那結果的排序是：O(N* LOG N)。 如果比較是O(1)我們有：O(1*N) = O(N)進行排序。

它可能在並行計算機體系結構上並行排序alg。 但在非平行計算機上不可能有O(1*N)