java - 查找和最小化归并排序算法运行时分析

Question

假设我有一个大小为 n 的数组，我想将它分配给大小为 n/k 的 k 个新数组。-这一步的运行时间可能是多少？****我想自从我们拆分数组时到 2 我们看它像 2^x=n =>x=log N => O(log n) 那么它在这里也一样：k^(n/k)=n => n/k=log N ****但是接下来呢？

现在我在每个 k 数组上运行冒泡排序算法-O(n^2) 并在所有 k 数组上使用合并算法来制作大小为 n 的排序数组-假设合并复杂度为 O(kn ）。

另外我不想找到一个 K 来最小化算法的运行时间，我该怎么做？我认为对运行时函数求导并找到它的最小值就可以了，这是正确的方法吗？

标签： javaarraysalgorithmcomplexity-theorymergesort

Answer 1

合并排序将数组拆分为连续的小块，直到它变成一堆 2 元素子数组。然后它开始将合并算法应用于连续更大的子数组。

想象一下，您有一个包含 16 个元素的数组。合并排序是这样进行合并的：

8 merges of two 1-item subarrays
4 merges of two 2-item subarrays
2 merges of two 4-item subarrays
1 merge of two 8-item subarrays

有四 (log ₂ (16)) 遍，并且在每遍中它检查每个项目。每遍都是O（n）。所以这个归并排序的运行时间是 O(n * log ₂ (n))。

现在，假设您有一个包含 81 个项目的数组，并且您想使用 3 路归并排序来合并它。现在您有以下合并序列：

27 merges of three 1-item subarrays (gives 27 3-item subarrays)
 9 merges of three 3-item subarrays (gives 9 9-item subarrays)
 3 merges of three 9-item subarrays (gives 3 27-item subarrays)
 1 merge of three 27-item subarrays

有四个 (log ₃ (81)) 通过。每次合并是 O(m * log ₂ (k))，其中 m 是要合并的项目的总数，k 是列表的数量。所以第一遍有 27 次合并，进行 3*log ₂ (3) 次比较。下一遍有 9 次合并，进行 9*log ₂ (3) 比较等。最终总合并为 O(n * log ₃ (n) * log ₂ (3))

您可以看到 3 路归并排序让您执行更少的传递（16 个项目的 3 路归并排序只需要 3 遍），但每次传递的成本要高一些。您必须确定的是：

n * log _k (n) * log ₂ (k) < n * log ₂ (n)

k您要将数组拆分成的子数组的数量在哪里。我会让你做这个数学。

但是，您必须小心，因为渐近分析没有考虑到现实世界的影响。例如，2 路合并非常简单。当您进行 k > 2 的 k 路合并时，您最终不得不使用堆或其他优先级队列数据结构，这具有相当多的开销。因此，即使上面的数学告诉您 3 路合并排序应该更快，您仍需要将其与标准的 2 路合并进行基准测试。

更新

你是对的。如果你简化方程，你最终会得到相同的方程。因此，无论 k 的值如何，计算复杂度都是相同的。

这是有道理的，因为如果 k = x，那么你最终会得到一个堆排序。

因此，您必须确定是否存在随着 k 增加而增加的合并开销被减少的通过次数所抵消的点。您可能需要凭经验确定。