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

Question

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

我想找到一个下界。

因为与只有两个可能结果的常规比较不同， super 比较将有 3 个!可能的结果，我认为应该是 log3(n!)。

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

Answer 1

其实超比次数是log_6(n!) ，这是因为每个 super 比较操作有 6 个可能的结果，而不是 3 个(3!= 6)。因此，通过在表示随机排列的树上重复调用这些 super 比较，您将得到 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)

P.S 一个很好的直觉是看看在“无穷大”处发生了什么，即你有一个排序 n 的 super 比较。元素。显然，您将需要一个这样的操作来对数组进行排序，实际上是 log_n!(n!) = 1。 , 而 log_n(n!) > 1 .