A Note on Average-Case Sorting
A Note on Average-Case Sorting
复制标题
关于平均情况排序的注意事项
作者：
S. Moran;A. Yehudayoff
本文研究了当输入存在已知分布且目标是最小化期望比较次数时，对\(n\)个元素进行排序的平均情况比较复杂度。我们推广了弗雷德曼算法（它是插入排序的一种变体），并给出了一个基本紧的上界：如果\(\mu\)是\(n\)个元素的排列上的一种分布，那么可以用至多\(H(\mu)+2n\)次期望比较次数对来自\(\mu\)的输入进行排序，其中\(H\)是熵函数。该算法对更有可能出现的输入使用更少的比较次数：对于每个排列\(\pi\)，该算法通过使用至多\(\log_{2}(\frac{1}{Pr_{\mu}(\pi)}) + 2n\)次比较来对\(\pi\)进行排序。\(H(\mu)\)始终是期望比较次数的一个下界，并且对\(n\)的线性依赖也是必需的。
This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize the expected number of comparisons. We generalize Fredman’s algorithm which is a variant of insertion sort and provide a basically tight upper bound: If μ is a distribution on permutations on n elements, then one may sort inputs from μ with expected number of comparisons that is at most H(μ) + 2n, where H is the entropy function. The algorithm uses less comparisons for more probable inputs: For every permutation π, the algorithm sorts π by using at most log2(1Prμ(π))+2ndocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$log _{2}(frac {1}{Pr _{mu }(pi )})+2n$end{document} comparisons. A lower bound on the expected number of comparisons of H(μ) always holds, and a linear dependence on n is also required.