我在研究合并排序主题时遇到了这个概念，即合并排序中的比较次数（在最坏的情况下，根据维基百科）等于 (n ⌈lg n⌉ - 2 ⌈lg n⌉</支持> + 1); 实际上它介于 (n lg n - n + 1) 和 (n lg n + n + O(lg n)) 之间。问题是我无法弄清楚这些复杂性试图表达什么。我知道 O(nlogn) 是合并排序的复杂性，但是比较的次数？
问问题
19905 次
1 回答
8
为什么要计算比较
任何排序算法基本上都有两种操作：比较数据和移动数据。在许多情况下，比较会比搬家更昂贵。想想基于引用的类型系统中的长字符串：移动数据只会交换指针，但比较可能需要在找到第一个差异之前迭代字符串的大部分公共部分。所以从这个意义上说，比较很可能是需要关注的操作。
为什么要精确计数
这些数字似乎更详细：您得到一个实际数字，而不是简单地给出一些朗道符号（大哦符号）来表示复杂性。一旦您确定了基本操作是什么，例如本例中的比较，这种实际计数操作的方法就变得可行了。在比较被朗道符号隐藏的常数时，或者在检查小输入的非渐近情况时，这一点尤其重要。
为什么这个精确的计数公式
请注意，在整个讨论中，lg 表示以 2 为底的对数。当您对n 个元素进行合并排序时，您有 ⌈lg n ⌉ 个合并级别。假设您在每个要排序的元素上放置 ⌈lg n ⌉ 个硬币，并且合并需要一个硬币。这肯定足以支付所有合并的费用，因为每个元素都将包含在 ⌈lg n ⌉合并中，并且每次合并所进行的比较不会超过所涉及的元素数量。所以这是公式中的n ⌈lg n ⌉ 。
由于两个长度为m和n的数组的合并只需要进行m + n - 1 次比较，所以最后你仍然有硬币，每次合并都有一个。让我们暂时假设我们所有的数组长度都是 2 的幂，即你总是有m = n。那么合并的总数是n -1（2的幂之和）。利用n是 2 的幂这一事实，这也可以写为 2 ⌈lg n ⌉ </sup> - 1，然后从所有硬币的数量中减去返回硬币的数量，得到n ⌈lg n ⌉ - 2 ⌈lgn _⌉</sup> + 1 根据需要。
如果n小于 1 小于 2 的幂，则存在 ⌈lg n ⌉合并，其中少一个元素。这包括两个单元素列表的合并，这些列表过去只取一枚硬币，现在完全消失了。所以总成本减少了 ⌈lg n ⌉，如果n是 2 的幂，这正是你放在最后一个元素上的硬币数量。所以你必须在前面放置更少的硬币，但你会得到相同数量的硬币。这就是公式使用 2 ⌈lg n ⌉ </sup> 而不是n的原因：除非您降低到较小的 2 次方，否则该值保持不变。如果n之间的差异，同样的论点成立并且二的下一个幂大于 1。
总的来说，这导致了维基百科中给出的公式：
n ⌈lg n ⌉ − 2 ⌈lg n ⌉ </sup> + 1
注意：我对上述证明非常满意。对于那些喜欢我的公式的人，请随意分发它，但不要忘记根据许可证的要求将其归功于我。
为什么这个下限
为了证明下界公式，让我们写 ⌈lg n ⌉ = lg n + d其中 0 ≤ d < 1。现在上面的公式可以写成
n (lg n + d ) − 2 lg n + d + 1 =
n lg n + nd - n 2 d + 1 =
n lg n - n (2 d - d ) + 1 ≥
n lg n - n + 1
其中不等式成立，因为 2 d − d ≤ 1 for 0 ≤ d < 1
为什么这个上限
我必须承认，我很困惑为什么有人将n lg n + n + O(lg n ) 命名为上限。即使您想避免使用 floor 函数，上面的计算也建议将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)) 之间
如果第一部分为真，那么第二部分也同样为真，但明确说明上限似乎毫无意义。我自己没有看细节，但是这两个陈述像这样放在一起看起来很奇怪。要么第一个真的是真的，在这种情况下我会省略第二个，因为它只会令人困惑，或者第二个是真的，在这种情况下第一个是错误的，应该省略。
于 2012-09-10T06:09:27.997 回答