python - 递归深度和一个事实？

Question

我看到这段文字：

出现一个问题：

但是你在正常的快速排序中看到，当我们在一个子数组中有 1 个元素，在下一个子数组中有 n-1 个元素时，我们在使用堆栈时得到 O(n) 的深度。这与这个事实相反吗？问题出在哪里？

我对这个话题的误解在哪里？

标签： pythonalgorithmsortingdata-structuresquicksort

Answer 1

The important part is "constant fraction of the elements". If you hit a degenerate Quicksort case where the partitioning puts a constant number (e.g. 1) of elements on one side of the partition, you'll get O(n^2) time complexity.

But if every partitioning call puts a constant fraction (e.g. 99%) of elements on one side, you'll still get O(n log n) (albeit with a larger constant factor).