algorithm - 合并排序 O(n log n) 每个级别的操作数

Question

这是一个我已经回避了很长时间的问题，但是即使在阅读了其他答案之后，我也很难理解为什么归并排序是 O(n * log n)。可能是我忽略了一些愚蠢的事情。

我所理解的是 log n 来自二叉树的高度。
我不明白为什么树中每一层的高度都需要 n 次操作。
或者，也许我在看这个完全错误的方式（？）。

假设我有一个 n = 8 的情况：

[1, 5, 2, 3, 4, 8, 1, 9]

...然后我构建二叉树，拆分每个级别：

最终我会得到（方便排序）：

[1, 5], [2, 3], [4, 8], [1, 9] 

我看不出合并这些将如何导致第一级上的 8 个操作（据我了解，n * log(n) 是级别数 * 每个级别的操作数。前两对的合并：

我最终得到了 3 次操作，即检查 2 与 1 和 5。
既然你知道 3 > 2，你不需要再检查第一对中的 1。
在最坏的情况下，我找不到每 2 对需要 4 次操作的情况。那么你如何最终得到每个级别 8 次操作呢？

我没有数学天赋，我现在还在学习。
因此，如果我以错误的方式看待这个问题，我深表歉意。

标签： algorithmsorting

Answer 1

查看将两个列表合并为一个的最后一步。如果列表共享相同的长度 n/2，则您最多需要 n-1 次比较，以寻找一个列表前面的最小元素，因为它们以相同的速度收缩。否则，您最终可能会减少操作。与其他层类似，您得到的操作数低于 n 次，该数字甚至应该略有减少。但是 O(n log n) 是一个上限，进一步检查会表明归并排序并不是渐近更好的。

进一步检查：设n=2^k。我们有 k 层。一层最多有 n-1 个操作，一层有两次 n/2 - 1 个操作……直到 n/2 乘以 1 个操作。我们应该得到 n-1 + 2(n/2 - 1) +4(n/4-1)... + n/2(1)= n-1 + n - 2 + n - 4 +... + n - n/2 = kn - (1+2+4+...+2^(k-1)) = kn - (2^k - 1) = n log n - n +1。

n log n 比 n 和 1 增长得快，所以我们甚至得到 θ(n log n)，因为我们只对增长最快的部分感兴趣。