任何排序算法基本上都有两种操作:比较数据和移动数据.在许多情况下,比较比移动更昂贵.考虑基于参考的输入系统中的长字符串:移动数据将简单地交换指针,但是比较可能需要在找到第一个差异之前迭代字符串的大部分公共部分.所以在这个意义上,比较可能是关注的操作.
这些数字看起来更加详细:不是简单地给出一些Landau符号(大哦符号)的复杂性,而是得到一个实际的数字.一旦确定了基本操作是什么,比如在这种情况下进行比较,这种实际计算操作的方法就变得可行了.在比较Landau符号隐藏的常数或检查小输入的非渐近情况时,这一点尤其重要.
需要注意的是整个讨论中,LG表示与基地2对数在合并排序ñ元素,你有⌈lg ň ⌉合并的水平.假设你把⌈lg ň ⌉硬币每个元素进行排序,以及合并成本的一种硬币.这无疑将足以支付所有的合并,因为每个元素将被列入⌈lg ñ ⌉合并,每个合并不会采取更多的比较小于有关元素的数量.因此,这是ñ ⌈lg ñ ⌉从您的公式.
由于两个长度为m和n的数组的合并仅需要m + n - 1个比较,因此您仍然在末尾留下硬币,每个合并一个.让我们暂时假设我们所有的数组长度都是2的幂,即你总是有m = n.然后合并的总数是n - 1(2的幂的总和).使用的事实,Ñ是二的幂,这也可以写为2 ⌈lg Ñ ⌉ - 1,并减去该号码返回硬币从所有的硬币收益的数量Ñ ⌈lg Ñ ⌉ - 2 ⌈lg Ñ ⌉根据需要加1.
如果Ñ大于二的幂小于1,则有⌈lg Ñ ⌉合并一个元件少涉及.这包括两个单元素列表的合并,这些列表用于获取一枚硬币并且现在完全消失.所以总成本由⌈lg减少ñ ⌉,而这正是你必须放置在最后一个元素,如果硬币数ñ是二的幂.所以你必须预先放置较少的硬币,但你会得到相同数量的硬币.这就是为什么公式有2个原因⌈lg ñ ⌉代替ñ:除非你降低到两个较小的功率值保持不变.如果n和下一个2的幂之间的差值大于1,则相同的论证成立.
总的来说,这导致了维基百科中给出的公式:
Ñ ⌈lg Ñ ⌉ - 2 ⌈lg Ñ ⌉ + 1
注意:我对上述证据非常满意.对于那些喜欢我的配方的人,请随意分发它,但不要忘记将其归因于许可证要求.
到坡口下界式,让我们写出⌈lg Ñ ⌉= LG Ñ + d 0≤ d <1.现在上面的公式可以写成
Ñ(LG Ñ + d) - 2- LG Ñ + d + 1 =
Ñ LG ñ + ND - ñ 2 d + 1 =
ñ LG ñ - ñ(2 d - d)+ 1≥
ñ LG ñ - ñ + 1
,其中不等式成立,因为2 d - d ≤1 0≤ d <1
我必须承认,我很困惑为什么有人会将n lg n + n + O(lg n)命名为上限.即使你想避免地面函数,上面的计算也表明n lg n - 0.9 n + 1是一个更精确的公式上限.2 d - d具有其最小值(LN(LN(2))+ 1)/ LN(2)≈0.914 d = -ln(LN(2))/ LN(2)≈0.529.
我只能猜测引用的公式出现在某个出版物中,或者作为该算法的相当松散的界限,或者作为与该算法进行比较的其他算法的确切比较数.
以下评论已解决此问题; 一个公式最初被错误引用.
等于(n lg n - n + 1); 实际上它介于(n lg n - n + 1)和(n lg n + n + O(lg n))之间
如果第一部分是真的,那么第二部分也是如此,但是明确地指出上限似乎是毫无意义的.我自己没有看过细节,但这两个陈述在这样的时候看起来很奇怪.要么第一个真的是真的,在这种情况下我会省略第二个,因为它只是令人困惑,或者第二个是真的,在这种情况下第一个是错误的,应该省略.