arrays - 如何找到涉及超级比较的排序算法的下限？

Question

假设有一种排序算法，除了常规比较之外，还允许进行超级比较：超级比较接受三个元素并按从小到大的顺序输出这些元素。

我想找到一个下限。

由于与只有两种可能结果的常规比较不同，超级比较将有 3 个！可能的结果，我认为应该是log3(n!)。

我不确定，有什么想法吗？

Answer 1

实际上，超级比较的数量是log_6(n!)，这是因为每个超级比较操作有 6 个可能的结果，而不是 3 个（3！= 6）。因此，通过在表示随机排列的树上重复调用这些超级比较，您可以在log_6(n!)比较操作中得到一个排序数组。

请注意，当涉及到渐近时间复杂度时 - 它仍然O(nlogn)是对数的底并不重要，因为您可以轻松地切换底：

log_6(n!) = log_2(n!)/log_2(6) = log_2(n!) / CONST 
=> log_6(n!) is in O(log_2(n!))
=> log_6(n!) is in O(nlogn)

PS一个很好的直觉是看看在“无穷大”会发生什么，即你有一个对n元素进行分类的超级比较。显然，您将需要一个这样的操作来对数组进行排序，实际上是log_n!(n!) = 1while log_n(n!) > 1。

Answer 2

在 ocaml 中，

let rec quicksort = function
    | [] -> []
    | x::xs -> let smaller, larger = List.partition (fun y -> y < x) xs
               in quicksort smaller @ (x::quicksort larger)