algorithm - 快速排序的时间和空间复杂度？

Question

Quick 是不使用任何辅助数组的就地算法。那么为什么这个 O(nlog(n)) 的内存复杂度呢？

同样，我知道最坏情况的时间复杂度是 O(n^2)，但不明白为什么平均情况时间复杂度是 O(nlog(n))。基本上我不确定我们所说的平均案例复杂度是什么意思？

标签： algorithmquicksort

Answer 1

第二点，摘自维基百科：

最不平衡的分区发生在分区例程返回大小为 n - 1 的子列表之一时。如果主元恰好是列表中的最小或最大元素，或者在某些实现中（例如，所述的 Lomuto 分区方案上面）当所有元素都相等时。

如果这种情况在每个分区中重复发生，那么每个递归调用都会处理一个大小比前一个列表小一的列表。因此，我们可以在到达大小为 1 的列表之前进行 n-1 次嵌套调用。这意味着调用树是 n-1 次嵌套调用的线性链。第 i 个调用确实 O(n - i) 工作来进行分区，并且 {\displaystyle \textstyle \sum _{i=0}^{n}(ni)=O(n^{2})} ，所以在这种情况下快速排序需要 O(n²) 时间。

因为您通常不知道要排序的确切数字，也不知道选择哪个枢轴元素，所以您有机会知道您的枢轴元素不是您排序的数组中的最小或最大数字。如果您有一个包含n 个不重复数字的数组，则您有 (n - 2) / n 的机会，即您没有最坏的情况。