DSA 特定算法的时间复杂度

请查看 此页面 以了解时间复杂度的总体解释。

快速排序的时间复杂度

该 快速排序 算法选择一个值作为“枢纽”元素，并将其他值移动，以便较高的值位于枢纽元素的右侧，较低的值位于枢纽元素的左侧。

然后，快速排序算法继续递归地对枢纽元素左侧和右侧的子数组进行排序，直到数组排序完成。

最坏情况

要找到快速排序的时间复杂度，我们可以先从最坏情况开始分析。

快速排序的最坏情况是数组已经排序。在这种情况下，每次递归调用后只有一个子数组，并且新子数组只比前一个子数组少一个元素。

这意味着快速排序必须递归调用自身 \(n\) 次，并且每次它都必须平均进行 \(\frac{n}{2}\) 次比较。

最坏情况下的时间复杂度是

\[ O(n \cdot \frac{n}{2}) = \underline{\underline{O(n^2)}} \]

平均情况

平均而言，快速排序实际上要快得多。

快速排序平均速度快是因为每次快速排序递归运行时，数组都被大致分成两半，因此子数组的大小会迅速减小，这意味着不需要进行太多递归调用，并且快速排序能够比最坏情况更快地完成。

下图显示了当使用快速排序进行排序时，一个包含 23 个值的数组是如何分成子数组的。

枢纽元素（绿色）被移动到中间，数组被分成子数组（黄色）。有 5 个递归级别，包含越来越小的子数组，其中大约 \(n\) 个值在每个级别上以某种方式被触碰：比较、移动或两者兼而有之。

\( \log_2 \) 告诉我们一个数字可以被分成 2 的次数，所以 \( \log_2 \) 是一个很好的估计，可以用来估算递归级别的数量。\( \log_2(23) \approx 4.5 \)，这是对上面特定例子中递归级别的数量的一个足够好的近似值。

实际上，子数组并不总是在每次递归时被精确地分成两半，而且并非在每个级别上都有精确的 \(n\) 个值被比较或移动，但我们可以说这是平均情况，从而找到时间复杂度

\[ \underline{\underline{O(n \cdot \log_2n)}} \]

下面你可以看到，与之前的冒泡排序、选择排序和插入排序算法相比，快速排序在平均情况下，时间复杂度有了显著提高。

快速排序算法中的递归部分实际上是平均排序场景速度如此之快的原因，因为对于枢纽元素的良好选择，每次算法调用自身时，数组都会被更均匀地分成两半。因此，即使值的数量 \(n \) 翻倍，递归调用的数量也不会翻倍。

快速排序模拟

使用下面的模拟，看看理论时间复杂度 \(O(n^2)\)（红线）与实际快速排序运行的操作次数之间的比较。

上面的红线代表最坏情况下的理论上限时间复杂度 \(O(n^2)\)，绿线代表随机值的平均情况时间复杂度 \(O(n \log_2n)\)。

对于快速排序，平均随机情况和数组已经排序的情况之间存在很大差异。你可以通过运行上面的不同模拟来看到这一点。

已经按升序排序的数组需要如此多的操作的原因是，它需要最多的元素交换，这是因为它的实现方式。在这种情况下，最后一个元素被选为枢纽元素，最后一个元素也是最大的数字。因此，每个子数组中的所有其他值都会被交换，以便落在枢纽元素的左侧（它们本来就位于那里）。