推广中位数算法的中位数
Generalizing the median of medians algorithm
我被要求找到大小为 g 的组的中位数算法的一般形式的 运行 时间。从常见的例子 g=3,5,7 和 T(n)=T(n/5)+T(2n/3)+cn、T(n)=T(n/5)+T(7n/10)+cn 和 T(n)=T(n/7)+T(5n/7)+cn 来看，奇数的一般情况是 T(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，但我不禁觉得我错过了一些东西。
任何人都可以就该算法如何处理偶数组提出建议吗？我想一旦我理解了算法，我应该能够找到 运行 时间。
您的分析是正确的；当g为偶数时，你可以将运行-时间表示为T(n) = T(n/g) + T(3n/4) + cn，这是你简化的表达式；无论 g 是偶数还是奇数，每当 g > 4 时都是 O(n) 的归纳证明是相同的。
要了解为什么这个等式是正确的，最简单的方法是思考具有奇数 g 的 T(n) 的表达式是如何推导出来的。 我们可以假设我们的输入列表 A 没有重复元素，不失一般性（通过稍微修改算法，或者将每个元素 A[i] 替换为元组 (A[ i], i) 和使用词典比较）。这使得分析更容易。
现在，中位数中位数 Quickselect 的 运行-时间基于它所做的三件事：
- 在大小为
ceil(n/g) 的 'medians' 列表上递归调用自身以找到 中位数中位数 M
cn 对项目进行分组，围绕 M 对列表进行分区，并找到每个小组 g 的中位数，并且 - 在所有元素小于
M 的分区、所有元素大于 M 的分区或立即 return. 上递归调用自身
忽略 ceil 和加法常数 O(1)，得到 T(n) = T(n/g) + T(New Partition Size) + cn。 New Partition Size 最大可以是多少？这是 max(# elements less than M, # elements greater than M).
当 g 为奇数时，我们有一半的 n/g 组的中位数小于 M（因此 (g-1)/2，加上 1中位数，该组中的元素小于 M），一半的中位数大于 M（同样，为每个此类组提供 (g+1)/2 'greater than 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.
我被要求找到大小为 g 的组的中位数算法的一般形式的 运行 时间。从常见的例子 g=3,5,7 和 T(n)=T(n/5)+T(2n/3)+cn、T(n)=T(n/5)+T(7n/10)+cn 和 T(n)=T(n/7)+T(5n/7)+cn 来看，奇数的一般情况是 T(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，但我不禁觉得我错过了一些东西。
任何人都可以就该算法如何处理偶数组提出建议吗？我想一旦我理解了算法，我应该能够找到 运行 时间。
您的分析是正确的；当g为偶数时，你可以将运行-时间表示为T(n) = T(n/g) + T(3n/4) + cn，这是你简化的表达式；无论 g 是偶数还是奇数，每当 g > 4 时都是 O(n) 的归纳证明是相同的。
要了解为什么这个等式是正确的，最简单的方法是思考具有奇数 g 的 T(n) 的表达式是如何推导出来的。 我们可以假设我们的输入列表 A 没有重复元素，不失一般性（通过稍微修改算法，或者将每个元素 A[i] 替换为元组 (A[ i], i) 和使用词典比较）。这使得分析更容易。
现在，中位数中位数 Quickselect 的 运行-时间基于它所做的三件事：
- 在大小为
ceil(n/g)的 'medians' 列表上递归调用自身以找到 中位数中位数M cn对项目进行分组，围绕M对列表进行分区，并找到每个小组 g 的中位数，并且- 在所有元素小于
M的分区、所有元素大于M的分区或立即 return. 上递归调用自身
忽略 ceil 和加法常数 O(1)，得到 T(n) = T(n/g) + T(New Partition Size) + cn。 New Partition Size 最大可以是多少？这是 max(# elements less than M, # elements greater than M).
当 g 为奇数时，我们有一半的 n/g 组的中位数小于 M（因此 (g-1)/2，加上 1中位数，该组中的元素小于 M），一半的中位数大于 M（同样，为每个此类组提供 (g+1)/2 'greater than 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.