为什么快速排序中的每个级别的调用栈都需要O（n）时间才能完成？

Question

我在网上找到了quicksort的解释：

“>

据说，调用堆栈的每个级别都需要O（n）时间才能完成。但是，随着调用堆栈的增加，我们进行的比较不是少于n吗？

我在网上找到了quicksort的这种解释：书面记录说，每层调用堆栈都需要O（n）时间才能完成。然而，随着我们往上走，我们做的比较不是少于n个吗...

Answer 1

O（n）时间复杂度忽略了常数因子。该语句将每个拆分视为原始n个元素的分数常数。除Lomuto类型的方案在递归调用中不包括支点元素外，理想的分割约为50％和50％。因此，在最深层产生2个元素的情况下，O（n）的常数因子将为2 / n（因为（2 / n）（n）== 2）。