c - 归并排序的复杂度是o(nlogn)

Question

我理解了合并排序的概念。但我很难分析合并排序的时间复杂度。我知道对于所有情况，即最坏情况、平均情况和最好情况，它都是 o(n log n) 。但我无法理解它是如何o(n log n) 的。在每次迭代中，我们都会将列表划分两次。所以这更像是在每一步都增加递归调用。那么它会是o(n log n)。

谁能解释一下吗？也可以解释一下 o(log n) 吗？

Answer 1

可以将其想象为对 128 张写有数字的纸进行排序。第一步是排列相邻的纸张。您必须触摸/移动所有 128 张纸才能做到这一点。下一步是将两人合并为四人一组。同样，您需要移动所有 128 张纸才能做到这一点。然后你分成 8 组、16 组、32 组、64 组，最后是 128 组。在每一步中，你都必须移动所有 128 张纸。您会注意到总共有 7 个级别。这是日志(128)。因此，您在 7 个级别移动 128 个工作表，即 O(128*7)，即 O(n log n)。

• 第 1 步:将 128 个单独的纸张排列为 64 对纸张
• 第 2 步:将 64 对纸张排列成 32 个已排序的组，每组 4 个
• 第 3 步:将 32 组 4 block 排列成 16 组 8 block
• 第 4 步:将 16 组(每组 8 个)排列成 8 组(每组 16 个)
• 第 5 步:将 8 组 16 人排列成 4 组 32 人
• 第 6 步:将 4 组 32 个排列成 2 组 64 个
• 第 7 步:将 2 组 64 颗星排列成最后 1 组 128 颗星