算法缩减(中间值中位数，快速排序)

Question

我试图更好地理解约简，目前我正在研究两种算法，“中间值”和“快速排序”。

我了解到，这两种算法都使用类似(实际上完全相同)的分区子程序来帮助解决它们的问题，这最终使它们非常相似。

Select(A[1...n],k):  // Pseudocode for median of medians
  m = [n/5]
  for i from 1 to m:
    B[i] = Select(A[5i-4..5i],3)
  mom = Select(B[1..m],m/2)

  r = partition(A[1..n],mom)  // THIS IS THE SUBROUTINE

  if k < r:
    return Select(A[1..r-1],k)
  else if k > r:
    return Select(A[r+1..n],k-r)
  else
    return mom

那么，对于这两种算法，“约简”这个词有什么意义吗？下面的任何一项都有意义吗？

• 中间值/快速排序的中位数可以缩减为分区子例程
• 中间值降低到快速排序
• 快速排序降低到中间值。

Answer 1

我不认为这两种方法都可以简化为另一种(无论如何，以任何有意义的方式)。您可以使用中间值来选择快速排序的枢轴(但实际上几乎没有人这样做)。但是，Quicksort仍然需要执行其他一些基于pivot元素的步骤(具体来说，是基于pivot对数据进行分区)。

同样，中间值的中位数不能降低到快速排序，因为快速排序会做额外的工作，而这些工作(以及其他事情)会阻止它满足中间值的复杂性保证。