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

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)？

Answer 1

在第一次分区过程中，您将拆分成两个分区。这需要O(n)。在下一遍中，您有两个分区，每个分区的大小为n/2。对每个分区进行分区需要O(n/2)。第二遍的总时间是O(n/2 + n/2)：O(n)。每一遍都有更多的分区，但分区更小。总共进行log(n)次传递，每次传递总时间为O(n)次。

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