algorithm - 合并排序文件所需的比较总数

Question

给定 4 个包含 15、3、9 和 8 条记录的排序文件，将它们合并为一个排序文件所需的比较总数是多少？

假设我们为此使用合并步骤(来自合并排序)。

我知道合并步骤需要 O(N) 时间来执行。但是它进行了多少次比较？

Answer 1

如果您假设您使用典型合并排序中的合并步骤，这意味着您一次只能合并 2 个列表，这会使事情变得更简单。我们至少需要 3 次合并才能将 4 个列表变成 1 个。我们可以拆分列表，但这是在丢弃信息，我们最终只需要将它们合并回去，所以我怀疑这是否有帮助(没有证明它)。

那么唯一的问题就是合并列表的顺序。从两个列表中合并总共 k 元素的最坏情况比较次数是 k-1[*]，因此我们希望最小化元素总数所有合并。我认为(同样，没有证明)在这种情况下，这是通过从最小到最大成对合并来完成的，即 8+3 然后是 11+9 然后是 20+15。在最坏的情况下，总共有 10+19+34 = 63 记录比较。

一个不太巧妙的合并选择，比如 15+3 然后是 8+9 然后是 18+17，将需要更多的比较最坏的情况 (67)，但在开始之前您不需要知道列表的长度。

[*] 归纳证明:

当 k=1 时，需要 0 次比较，因为我们有一个空列表和一个长度为 1 的列表。

假设总长度为 j 的列表为真(对于某些 j >= 1)。然后在最坏的情况下，要合并两个长度为 j+1 的排序列表，我们首先比较两边的最小元素，移除较小的元素并将其插入输出列表。剩下的就是合并两个列表中剩余的内容，即总长度 j。我们可以通过归纳假设在最坏的 j-1 次比较中做到这一点。因此，总共 j+1 个元素最多需要 j 次比较，从而完成归纳。