合并排序与随机拆分

Question

在合并排序算法中，不是将数组分成相等的一半，而是尝试在每次调用时从随机点拆分数组，我想计算这个算法的平均时间？

我们的笔记将其计算为正常的归并排序。任何正式的想法？

Answer 1

这里证明它的时间复杂度是O(n log n)（不是很正规）

如果最大部分的大小最多为初始子数组的 3/4（它看起来是这样的：bad bad good good good good bad bad 用于数组，则我们调用拆分 "good"有 8 个元素）。拆分好的概率是1/2。这意味着在两次拆分中，我们期望一二是 "good"。

让我们画一棵递归合并排序调用树：

    [a_1, a_2, a_3, ..., a_n]    --- level 1
         /             \
[a_1, ..., a_k]   [a_k + 1, a_n] --- level 2
    /    \            /  \
...                              --- level 3

                                 ...

                                 --- level m

显然每一层最多有n个元素，所以时间复杂度为O(n * m).

但是 1)。表示层数为2 * log(n, 4 / 3)，其中log(a, b)是以a为底b的对数，即O(log n).
因此，时间复杂度为O(n * log n)。

Answer 2

我假设你在谈论递归归并排序。

在标准归并排序中，您在中点拆分数组，因此您最终在每个级别得到（大部分）相同大小的子数组。但是如果你在其他地方分裂，那么除了病理情况外，你最终得到的子数组数量几乎相同。

这样看：标准合并排序的分而治之方法导致 log n "levels" 排序，每个级别包含所有 n 项。您在每个级别进行 n 比较以对子数组进行排序。这就是 n log n 的来源。

如果你随机拆分你的数组，那么你必然会有更多的层次，但并不是所有的项目都在所有的层次上。也就是说，较小的子数组先于较长的子数组生成单项数组。因此，并非所有项目都在算法的所有级别进行比较。这意味着某些项目比其他项目更频繁地被比较，但平均，每个项目被比较 log n 次。

所以你真正要问的是，给定项目总数 N 分成 k 个排序数组，如果每个 k 个数组的长度相同，而不是 k 个数组是不同的长度。

答案是否定的。无论单个数组的长度如何，合并 k 个排序数组中的 N 个项目都需要相同的时间。有关示例，请参阅 How to sort K sorted arrays, with MERGE SORT。

所以你的问题的答案是平均情况（最好的情况）进行随机拆分的递归合并排序将是 O(n log n) ，堆栈 space 使用 O(log n)。最坏的情况，只有当你的随机拆分总是将数组拆分为一个包含单个项目的子数组，另一个包含余数的子数组时才会发生，这将需要 O(n) 堆栈 space，但仍然只需要 O( n log n) 时间。

请注意，如果您使用迭代合并排序，则在时间或 space 用法上没有渐近差异。

合并排序与随机拆分

Merge Sort with Random Split

sorting

algorithm

time-complexity

data-structures