DSA 归并排序时间复杂度

参见 此页面 了解时间复杂度的基本解释。

归并排序时间复杂度

该 归并排序算法 将数组分解成越来越小的部分。

当子数组合并在一起以使最低值排在最前面时，数组将被排序。

需要排序的数组有 \(n\) 个值，我们可以通过查看算法所需的运算次数来找到时间复杂度。

归并排序的主要操作是拆分，然后通过比较元素进行合并。

为了将数组从开始拆分到子数组仅包含一个值，归并排序总共做了 \(n-1\) 次拆分。想象一个有 16 个值的数组。它被拆分一次，变成长度为 8 的子数组，再拆分一次又一次，子数组的大小减少到 4、2，最后是 1。对于一个有 16 个元素的数组，拆分的次数是 \(1+2+4+8=15\)。

下图显示了对于一个有 16 个数字的数组，需要 15 次拆分。

合并的次数实际上也是 \(n-1\)，与拆分次数相同，因为每次拆分都需要合并来将数组重新组合在一起。对于每次合并，都会对子数组中的值进行比较，以使合并的结果排序。

在合并两个子数组时，产生最多比较的最坏情况是，如果子数组的大小相同。考虑合并 [1,4,6,9] 和 [2,3,7,8]。在这种情况下，需要进行以下比较：

1. 比较 1 和 2，结果： [1]
2. 比较 4 和 2，结果： [1,2]
3. 比较 4 和 3，结果： [1,2,3]
4. 比较 4 和 7，结果： [1,2,3,4]
5. 比较 6 和 7，结果： [1,2,3,4,6]
6. 比较 9 和 7，结果： [1,2,3,4,6,7]
7. 比较 9 和 8，结果： [1,2,3,4,6,7,8]

在合并结束时，只有一个值 9 在一个数组中，另一个数组为空，因此不需要比较就可以将最后一个值放入，合并后的结果数组为 [1,2,3,4,6,7,8,9]。我们可以看到，我们需要 7 次比较才能合并 8 个值（每个初始子数组中 4 个值）。一般来说，在最坏情况下，需要 \(n-1\) 次比较才能得到一个包含 \(n\) 个值的合并数组。

为了简单起见，假设我们在合并 \(n\) 个值时需要 \(n\) 次比较而不是 \(n-1\) 次。当 \(n\) 很大，我们想要使用大 O 符号计算上限时，这是一个可以接受的假设。

因此，在每层合并时，需要 \(n\) 次比较，但是有多少层呢？对于 \(n=16\)，我们有 \(n=16=2^4\)，因此有 4 层合并。对于 \(n=32=2^5\)，有 5 层合并，并且在每一层，都需要 \(n\) 次比较。对于 \(n=1024=2^{10}\)，需要 10 层合并。为了找出 2 的哪个幂等于 1024，我们使用以 2 为底的对数。答案是 10。数学上，它看起来像这样：\( \log_{2}1024=10\)。

正如我们从上图中看到的，每层都需要 \(n\) 次比较，并且有 \( \log_{2}n\) 层，因此总共有 \( n \cdot \log_{2}n\) 次比较操作。

时间复杂度可以根据拆分操作的数量和合并操作的数量来计算

\[ \begin{equation} \begin{aligned} O( (n-1) + n \cdot \log_{2}n) {} & = O( n \cdot \log_{2}n ) \end{aligned} \end{equation} \]

由于 \( n \cdot \log_{2}n\) 在较大的 \( n\) 时会占主导地位，并且由于我们计算算法的时间复杂度的方式，因此可以在上面的大 O 计算中删除拆分操作数量 \((n-1)\)。

下图显示了在包含 \(n\) 个值的数组上运行归并排序时时间如何增加。

归并排序的最佳和最坏情况之间的差异不像许多其他排序算法那样大。

归并排序模拟

对数组中的不同值数量运行模拟，看看归并排序在一个包含 \(n\) 个元素的数组上所需的运算次数是 \(O(n \log n)\)

如果我们保持值的数量 \(n\) 固定，则 "随机"、"降序" 和 "升序" 所需的操作次数几乎相同。

归并排序每次执行的效果几乎相同，因为无论数组是否已排序，它都会被拆分并使用比较进行合并。