2

我被要求为大小为 g 的组找到中位数算法的一般形式的运行时间。从、 和的常见示例g=3,5,7中T(n)=T(n/5)+T(2n/3)+cn，奇数的一般情况似乎是。T(n)=T(n/5)+T(7n/10)+cnT(n)=T(n/7)+T(5n/7)+cnT(n)=T(n/g)+T(1-(n/(2g)*(g+1)/2))+cn

但是，我正在努力使用什么作为偶数 g 的中位数，其中中位数将存在于两个元素之间，而不是实际存在于集合本身中。有人告诉我，我可以忽略地板和天花板。直觉告诉我它应该只是T(n)=T(n/g)+T(1-(n/(2g)*(g)/2))+cn，但我不禁觉得我错过了一些东西。

任何人都可以就算法如何处理偶数组提供建议吗？我想一旦我理解了算法，我应该能够找到运行时间。

4

1 回答 1

2

你的分析是正确的；当 g 为偶数时，您可以将运行时间表示为 T(n) = T(n/g) + T(3n/4) + cn，这是您的简化表达式；无论 g 是偶数还是奇数，当 g > 4 时这是 O(n) 的归纳证明是相同的。

要了解为什么这个等式是正确的，最容易考虑的是如何导出具有奇数 g 的 T(n) 的表达式。我们可以假设我们的输入列表 A 没有重复元素，而不会失去一般性（通过稍微修改算法，或者将每个元素 A[i] 替换为元组 (A[i], i) 并使用字典比较） . 这使得分析更加容易。

现在，Median-of-Medians Quickselect 的运行时基于它所做的三件事：

  1. 在大小的“中位数”列表上递归调用自身ceil(n/g)以找到中位数的中位数 M
  2. cn对项目进行分组，围绕 划分列表M，并找到每个 g 小组的中位数，以及
  3. 在所有元素小于M的分区、所有元素大于 的分区上递归调用自身M，或者立即返回。

忽略 ceil 和一个附加O(1)常数，这给出T(n) = T(n/g) + T(New Partition Size) + cn. 新分区大小可以是多大？是max(# elements less than M, # elements greater than M)。

奇怪的时候g，我们有一半的n/g组中位数小于M（因此(g-1)/2，加上1中位数，该组中的元素小于M），一半的中位数大于M（再次，为每个这样的元素给出(g+1)/2“大于”M团体）。

由于您将偶数列表的中位数定义为两个中间元素的算术平均值，因此这变得更加简单：一半的n/g组的中位数小于M，并且每个此类组的恰好一半的元素小于其中位数，因此小于M; 相同的逻辑适用于大于。这意味着我们已经消除了至少 ( half of n/g times g/2) 或n/4元素，留下3n/4了最大的新分区大小和T(n) = T(n/g) + T(3n/4) + cn.

于 2021-09-21T05:26:23.230 回答