java - 将枢轴作为数组中最后一个元素的快速排序分析

Question

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

6 8 7 5 9 4

4 是我的透视元素。

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

Answer 1

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

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

<小时/>

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