在合并排序比较数(Number of Comparisons in Merge-Sort)

2019-06-28 03:03发布

我正在研究合并排序主题,我就遇到了这个概念,(按照最坏的情况,以及在合并排序的比较次数维基百科 )等于(n⌈lgn⌉ - 2⌈lgn⌉+ 1 ); 实际上它是(N LG N - N + 1)之间和(n LG N + N + O(LG n))的。 问题是,我无法弄清楚这些复杂试试再说。 我知道O(nlogn)是合并排序的复杂性,但比较的次数?

Answer 1:

为什么要算比较

基本上有两种操作任何排序算法:比较数据和移动数据。 在许多情况下,比较会比移动更昂贵。 想想一个参考基础的类型系统的长字符串:移动数据将简单地交换三分球,但比较找到的第一个差异之前,可能需要遍历字符串的大型公共部分。 所以在这个意义上,比较很可能是把重点放在操作。

为什么精确计数

这些数字显得更细致:不是简单地给出了一些复杂的符号朗多(大哦符号),你会得到一个实际数目。 一旦你决定的基本操作是什么,像在这种情况下进行比较,实际上计数操作的这种做法变得可行。 比较由朗道符号隐藏常数时,或检查的小输入的非渐进情况下时,这是特别重要的。

为什么这样精确计数公式

需要注意的是整个讨论中,LG表示与基地2对数在合并排序元素,你有合并的水平。 假设你把硬币每个元素进行排序,以及合并成本的一种硬币。 这无疑将足以支付所有的合并,因为每个元素将被列入合并,每个合并不会采取更多的比较小于有关元素的数量。 所以这是从您的公式。

如长度为的两个阵列和的合并只需要 + - 1个比较,仍然有硬币留在端部,一个从每个合并。 让我们暂时假定我们所有的数组长度是两个,即权力,你总是有 = 然后合并的总数为 - 1(2的幂次方总和)。 使用的事实是2的幂,这样也可以写为 - 1,并减去该号码返回硬币从所有的硬币产量的数目- + 1根据需要。

如果大于二的幂小于1,则有合并一个元件少涉及。 这包括用于拍摄一个硬币和两个一元素列表的合并现在完全消失。 所以总成本由减少,而这正是你必须放置在最后一个元素如果是二的幂币的数量。 所以,你必须预先放置较少硬币,但你得到相同数量的硬币。 这就是为什么公式有而不是原因:除非你降低到两个较小的功率值保持不变。 相同的论点成立,如果和两个下一个功率之间的差是大于1。

综合来看,这将导致中给出的公式在维基百科 :

- 1

注:我与上述证据非常高兴。 对于那些谁喜欢我的配方,随意分发,但不要忘记为它归因于我的许可要求。

为什么这个下界

到坡口下界式,让我们写出 LG + <1。现在上面的公式可以写成
+ - 2- LG + + 1 = LG + - 2 + 1 = LG - - - + 1个
其中不等式成立,因为2 - <1

为什么这个上限

我必须承认,我很是困惑,为什么有人会名称为 LG + + O(LG 为上限。 即使你想避免地板函数,计算上述建议的东西如 LG - 0.9 + 1的更严格的上限的精确公式。 2 - 具有其最小值(LN(LN(2))+ 1)/ = -ln(LN(2))/ LN≈0.914(2)≈0.529。

我只能猜测,引用的式在一些出版物发生时,无论是作为一个相当松散结合的这个算法,或为被针对该一个比较了某种其他算法比较的确切数目。


(两种不同的计数)

这个问题已经通过下面的评论解决; 一个公式最初引用不正确。

等于(n LG N - N + 1); 实际上它是(N LG N - N + 1)之间和(n LG N + N + O(LG n))的

如果第一部分是真实的,第二个是平凡也是如此,但明确地陈述上限似乎一种毫无意义的。 我没有看过的细节我自己,但是当这样一起这两个语句出现奇怪。 无论是第一个确实是真的,在这种情况下,我省略了第二个,因为它是唯一的混乱,或者第二个是真实的,在这种情况下,第一个是错误的,应该被忽略。



文章来源: Number of Comparisons in Merge-Sort