代码之家  ›  专栏  ›  技术社区  ›  R.. GitHub STOP HELPING ICE

媒体选择的最佳中值-3个元素块与5个元素块?

  •  10
  • R.. GitHub STOP HELPING ICE  · 技术社区  · 14 年前

    我正在研究一个基于 the Select algorithm

    让我困惑的是选择5元素块而不是3元素块。在我看来,你用5个元素的积木 n/4 = n/5 + n/25 + n/125 + n/625 + ... 5个操作的中间值,而对于3个元素块,则执行 n/2 = n/3 + n/9 + n/27 + n/81 + ... 三次手术中的一次。因为每5个中位数是6个比较,每3个中位数是2个比较,结果是 3*n/2 使用5的中位数和 n 使用3的中位数进行比较。

    有谁能解释这种差异,以及使用5元素块的动机是什么?我不熟悉应用这些算法的常规做法,所以也许有某种方法可以减少一些步骤,并且仍然“足够接近”中间值,以确保一个好的轴心点,并且这种方法在5元素块上更有效?

    3 回复  |  直到 14 年前
        1
  •  10
  •   Aryabhatta Aryabhatta    14 年前

    原因是,如果选择3个块,我们可能会失去使用O(n)时间算法的保证。

    对于5个块,时间复杂度为

    T(n)=T(n/5)+T(7n/10)+O(n)

    对于3个街区,结果是

    T(n)=T(n/3)+T(2n/3)+O(n)

    看看这个: http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf

        2
  •  6
  •   casablanca    14 年前

    我认为这与保证“良好”的分手有关。划分为5个元素块可确保最坏情况下的拆分为70-30。标准的论点是这样的: n/5 块中,至少有一半的中介是>=中介的中值,因此至少有一半的 块至少有3个元素(5的1/2)>=中间值,这将给出 3n/10 拆分,这意味着另一个分区是 7n/10 在最坏的情况下。

    这给了 T(n) = T(n/5) + T(7n/10) + O(n)

    自从 n/5 + 7n/10 < 1 ,最坏的运行时间是 O(n)

    因此,选择3个元素块可以: n/3 块至少有2个元素>=中间值,因此 2n/3 在最坏的情况下。

    T(n) = T(n/3) + T(2n/3) + O(n)

    在这种情况下, n/3 + 2n/3 = 1 ,所以它减少到 O(n日志n)

        3
  •  4
  •   Ecir Hana    8 年前

    你可以用3号块!是的,我和你一样惊讶。2014年(你在2010年问过)有一篇论文展示了如何做到这一点。

    这个想法是这样的:而不是 median3 , partition , 中间3 , 分区 中间3 , 中间3 , , 中间3 ,

    所以不是:

    T(n) <= T(n/3) + T(2n/3) + O(n)
    T(n) = O(nlogn)
    

    T(n) <= T(n/9) + T(7n/9) + O(n)
    T(n) = Theta(n)
    

    上述文章是 Select with Groups of 3 or 4 Takes Linear Time Select with groups of 3 or 4 (2015年,作者主页)。

    PS:那个 Fast Deterministic Selection