data-structures - 迭代快速排序的时间复杂度

Question

我已经了解了递归快速排序，最好的情况需要 O(nlogn)，最坏的情况需要 O(n^2)。但我试图找到迭代快速排序的时间复杂度。我知道最好的情况是 O(nlogn) 和 O(n^2)。但我不是为了最好的情况来证明它的合理性。我正在关注本教程

https://www.techiedelight.com/iterative-implementation-of-quicksort/

假设我们有 15 个元素，因此枢轴索引位置将始终位于中间，使其成为理想的最佳情况。但我发现它的条件是“while (!stack.empty())”，即分区数将发生 6 次，不接近 log(n)。如何证明迭代快速排序中最佳情况的时间复杂度是 O(nlogn)。？

标签： data-structurestime-complexitybig-ocomplexity-theoryquicksort

Answer 1

在第一个分区过程中，您拆分为两个分区。这需要 O(n)。在下一轮中，您有两个分区，每个分区的大小为 n/2。对其中的每一个进行分区需要 O(n/2)。第二遍的总时间为 O(n/2 + n/2): O(n)。每个通道都有更多的分区，但分区更小。总的来说，你进行了 log(n) 次传递，每一次都需要 O(n) 总时间。

它的工作方式与递归版本完全相同。唯一的区别是，在迭代版本中，您显式地管理堆栈，而不是依赖于递归版本中的隐式堆栈。