1

我试图更好地理解减少，我目前正在研究两种算法，“中位数的中位数”和快速排序。

我知道这两种算法都使用相似（实际上相同）的分区子例程来帮助解决它们的问题，最终使它们非常相似。

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

那么对于这两种算法，“减少”一词是否有意义？以下任何一项有意义吗？

  • Medians/Quicksort 的中值可以简化为一个分区子程序

  • 中位数的中位数减少到快速排序

  • 快速排序减少到中位数的中位数

4

2 回答 2

3

这实际上取决于您对“减少”的定义。

通常讨论的标准归约类型是映射归约（也称为多一归约）。从问题 X 到问题 Y 的映射简化如下：

给定问题 X 的输入 I X，将其转换为问题 Y 的输入 I Y 。然后，在 I Y上运行问题 Y 的求解器并输出该答案。

在映射缩减中，您可以对解决问题 Y 的子例程进行一次调用，并且您必须输出从该子例程返回的任何答案。例如，可以减少“这个数是偶数吗？”的问题。对于“这个数字是奇数吗？”的问题。通过将数字加一并输出结果数字是否为奇数。

作为映射缩减的非示例，请考虑以下两个问题：首先，问题“此列表中的每个布尔值都为真吗？”其次，问题“此列表中的某些布尔值是否为假？” 如果您有第二个问题的求解器，则可以通过运行第二个问题的求解器并输出相反的结果来使用它来解决第一个问题：布尔值列表具有一些错误的元素，当且仅当不是这种情况列表的每个元素都是真的。但是，这种归约不是映射归约，因为我们正在翻转子例程产生的结果。

经常使用的另一种归约类型是图灵归约。从问题 X 到问题 Y 的图灵简化如下：

假设有一个总是解决问题 Y 的魔法黑盒子，构建一个解决问题 X 的算法。

所有映射缩减都是图灵缩减，但不是相反。上述从“一切都是真的吗？”的简化。to "is something false" 不是映射缩减，而是图灵缩减，因为您可以使用子例程 for "is something false?" 了解列表是否包含任何错误值，然后可以输出相反的值。

映射约简和图灵约简之间的另一个主要区别是，在图灵约简中，您可以多次调用解决问题 Y 的子例程，而不仅仅是一个。

您可以将快速排序和中位数中位数视为使用分区作为子例程的算法。在快速排序中，该子例程完成了对所有内容进行排序所需的所有繁重工作，而在中位数中，它执行了缩小输入的基本步骤之一。由于这两种算法都对子程序进行了多次调用，因此您可以将它们视为图灵式的缩减。快速排序是从排序到分区的简化，而中位数是从选择到分区的简化。

希望这可以帮助！

于 2013-12-15T21:59:10.213 回答
0

我不认为任何一个都可以简化为另一个（无论如何，以任何有意义的方式）。您可以使用中位数的中位数来选择快速排序的枢轴（但实际上几乎没有人这样做）。不过，快速排序仍然需要基于枢轴元素执行一些其他步骤（特别是基于枢轴对数据进行分区）。

同样，中位数的中位数不能简化为快速排序，因为快速排序会做额外的工作，（除其他外）阻止它满足中位数中位数的复杂性保证。

于 2013-12-15T21:06:01.863 回答