Towards a Realistic Analysis of the QuickSelect Algorithm
Towards a Realistic Analysis of the QuickSelect Algorithm
复制标题
对 QuickSelect 算法进行现实分析
DOI：
--
复制
发表时间：
2015
影响因子：
0.5
通讯作者：
B. Vallée
中科院分区：
文献类型：
--
作者：
J. Clément;J. A. Fill;T. N. Thi;B. Vallée
我们重新回顾一下经典的QuickSelect算法的分析。通常，分析处理键比较的平均数量，但在这里我们将键视为由源生成的单词，并且单词通过其符号按字典顺序进行比较。我们的概率模型属于一大类信息源，其中包括无记忆（即独立符号）和马尔可夫源，以及许多无界相关源。算法的“实际”成本在这里是算法执行的符号比较的总数，并且在这种情况下，平均情况分析旨在提供对符号比较的平均数量的估计。对于 QuickSort 算法，已知平均情况复杂度结果为 θ(nlogn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt}egin{document}${Theta } (n log n)$end{document} 在关键比较的情况下，和 Θ(nlog2n)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}${Theta }(nlog ^{2} n)$end{document} 用于符号比较。对于 QuickSelect 算法，对于关键比较，平均情况复杂度为 θ(n)。在本文中，我们证明，就符号比较而言，QuickSelect 的平均情况复杂度仍然是 θ(n)。在每种情况下，我们都为主要常数提供了显式表达式，与源的概率行为密切相关。我们开始与 Philippe Flajolet 一起研究这个研究主题，并且本论文的简短版本（ICALP'2009 论文）是与他一起撰写的。与往常一样，菲利普发挥了核心作用，特别是在以下几点：快速算法的引入、源的驯服以及莱斯方法的使用。他还做了许多实验来展示渐近斜率 ρ(α) 并绘制了漂亮的图表，这些图表在本文中得到了重现。尽管扩展摘要没有提供任何对 QuickQuant 算法的分析证明，但 Philippe 还与我们一起为该证明设计了一个精确的计划，目前该计划已经完全编写完成。出于所有这些原因，我们本可以添加（并且当然希望添加）Philippe 作为本文的合著者。另一方面，菲利普对论文的撰写和组织方式极其严格，我们无法确定他是否会喜欢或验证我们的编辑选择。最后，这就是为什么我们决定不将他列为共同作者，而是怀着尊重和感情，将这篇论文献给他以纪念他。谢谢你，菲利普！
We revisit the analysis of the classical QuickSelect algorithm. Usually, the analysis deals with the mean number of key comparisons, but here we view keys as words produced by a source, and words are compared via their symbols in lexicographic order. Our probabilistic models belong to a broad category of information sources that encompasses memoryless (i.e., independent-symbols) and Markov sources, as well as many unbounded-correlation sources. The “realistic” cost of the algorithm is here the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons. For the QuickSort algorithm, known average-case complexity results are of Θ(nlogn)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}${Theta } (n log n)$end{document} in the case of key comparisons, and Θ(nlog2n)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}${Theta }(nlog ^{2} n)$end{document} for symbol comparisons. For QuickSelect algorithms, and with respect to key comparisons, the average-case complexity is Θ(n). In this present article, we prove that, with respect to symbol comparisons, QuickSelect’s average-case complexity remains Θ(n). In each case, we provide explicit expressions for the dominant constants, closely related to the probabilistic behaviour of the source. We began investigating this research topic with Philippe Flajolet, and the short version of the present paper (the ICALP’2009 paper) was written with him. As usual, Philippe played a central role, notably on the following points: introduction of theQuickValalgorithm, tameness of sources, and use of Rice’s method. He also made many experiments exhibiting the asymptotic slope ρ(α) and plotted nice graphs, which are reproduced in this paper. Even though the extended abstract does not provide any proof of the analysis of the algorithmQuickQuant, Philippe also devised with us a precise plan for this proof which has now completely been written. For all these reasons, we could have added (and certainly would have liked to add) Philippe as a co-author of this paper. On the other hand, Philippe was extremely exacting of how his papers were to be written and organised, and we cannot be sure that he would have liked or validated our editing choices. In the end, this is why we have decided not to include him as a co-author, but instead, to dedicate, with deference and affection, this paper to his memory. Thank you, Philippe!