java - 使用 Pivot 作为数组中最后一个元素的快速排序分析

Question

当您使用 QuickSort 时，我想知道这个数组的 Big-O 是什么：

6 8 7 5 9 4

4是我的 Pivot 元素。

我认为这将是复杂度为 的最佳情况O(nlogn)，但我不是 100% 确定。

标签： javaarraysbig-oquicksort

Answer 1

快速排序的 Big-O 复杂度是二次的 ( O(n^2))。这意味着对于每个可能的输入，它至少会执行得这么快（或者慢，如果你愿意的话）。

正如评论中提到的，Big-O 处理理论上的最坏情况，而不是特定的输入。对于特定输入，您可以计算绝对步数。

---

顺便说一句，快速排序（曾经？）非常受欢迎，不是因为它具有良好的 Big-O 性能，而是因为在中等输入大小上具有良好的通常情况下的性能——虽然有一些算法可以执行O(n log n)（这也是理论上的限制——不能做得更好)，它们在实际使用中往往较慢，因为它们具有较大的常数（即渐近更好的性能仅在较大的输入上表现出来）。