Comparison-based time-space lower bounds for selection

Comparison-based time-space lower bounds for selection
复制标题

基于比较的时空下界选择

DOI：
10.1145/1721837.1721842
复制
发表时间：
2009
期刊：
ACM Trans. Algorithms
影响因子：
--
通讯作者：
Timothy M. Chan
Timothy M. Chan
中科院分区：
--
文献类型：
--
作者：
Timothy M. Chan

文献摘要

被引文献

相似文献

我们建立了第一个非平凡的选择问题的时间-空间权衡的下界。我们证明，任何基于比较的随机算法，寻找中位数需要Ω（<i>n</i>log<sub><i>log</i></sub><i>Sn</i>）预期时间的RAM模型（或更一般的比较分支程序模型），如果我们有<i>S</i>位的额外空间，除了只读输入数组。这个界限对所有<i>S</i>log<i>n都</i>是紧的，即使数组是随机给定的，这个界限也是正确的。因此，我们的结果回答了Munro和拉曼[1996]提出的一个16年前的问题，并且还补充了最近限制于顺序访问的下限，如多通道流模型[Chakrabarti et al. 2008 b]。 我们还证明了，任何基于比较的，确定性的，多通道流算法找到中位数需要Ω（<i>n</i>log<sup>*</sup>（<i>n</i>/<i>s</i>）+<i>n</i>log<sub><i>s</i></sub><i>n</i>）最坏情况下的时间（在扫描加比较），如果我们有<i>s个</i>细胞的空间。这个界对所有的<i>s</i>_log<sup>2</sup><i>n</i>也是紧的。我们也得到了I/O有效算法的确定性下界。 本文中的证明是独立的，不依赖于通信复杂性技术。
We establish the first nontrivial lower bounds on time-space trade-offs for the selection problem. We prove that any comparison-based randomized algorithm for finding the median requires Ω(<i>n</i>log log<sub><i>S</i></sub> <i>n</i>) expected time in the RAM model (or more generally in the comparison branching program model), if we have <i>S</i> bits of extra space besides the read-only input array. This bound is tight for all <i>S</i> ≫ log <i>n</i>, and remains true even if the array is given in a random order. Our result thus answers a 16-year-old question of Munro and Raman [1996], and also complements recent lower bounds that are restricted to sequential access, as in the multipass streaming model [Chakrabarti et al. 2008b]. We also prove that any comparison-based, deterministic, multipass streaming algorithm for finding the median requires Ω(<i>n</i>log<sup>*</sup>(<i>n</i>/<i>s</i>)+ <i>n</i>log<sub><i>s</i></sub> <i>n</i>) worst-case time (in scanning plus comparisons), if we have <i>s</i> cells of space. This bound is also tight for all <i>s</i> ≫log<sup>2</sup> <i>n</i>. We get deterministic lower bounds for I/O-efficient algorithms as well. The proofs in this article are self-contained and do not rely on communication complexity techniques.