Rik*_*der 4 algorithm computation-theory median-of-medians
我一直在试图了解其中"5"来自于中位数算法的中位数,但似乎无法找到它是如何得出的简单描述,以及为什么它是最佳的.
例如,为什么不说7是一个可行的选择？
我可以看到5的唯一优势是它在中间的每一侧有2个项目,对5个项目进行排序,这是一个不超过3个交换的简单情况.
选择5是因为它是递归求解为O(n)的最小值.7也有效,但往往比较慢.
更具体地说:如果将输入分解为大小为5的块,则会出现这种情况:
T(n)≤T(n/5)+ T(7n/10)+ O(n)
这解决了O(n),因为工作在每个级别上几何衰减.
如果我们使用大小为3的块,我们就会得到
T(n)≥T(n/3)+ T(2n/3)+ O(n)
这解决了Ω(n log n).
选择大小为7的块给出
T(n)≤T(n/7)+ T(5n/7)+ O(n)
这也解决了O(n),因为工作在几何上衰减.然而,大O项中的常数大于5中的常数,因为排序和取大小为7的n/7块的中值比排序和取n/5块大小为5的中值更多. ,五个块的情况更常用.
希望这可以帮助!