Space 快速排序的复杂度
Space Complexity of Quick Sort
我了解到，在没有 Sedgewick 消除尾递归技巧的情况下，快速排序的 space 复杂度为 O(n)。但是，如果我们跟踪存储在堆栈上的调用，就会发现任何调用都是 O(log n) 步，如图所示。
图中，
在计算 (1,1) 的值时，我们存储 [(1,8), (1,4), (1,2)] ,
的调用
在计算 (3,3) 的值时，我们存储 [(1,8)、(1,4)、(3,4)] 等的调用
在蚂蚁时间点仅构成 O(log n) space。那么复杂度是不是变成了O(n)？
在您上面给出的树示例中，您展示了一个 运行 的快速排序，它总是恰好在每一步中选择准确的中值元素作为拆分点。这使得递归深度为 O(log n)，因此，如您所述，即使没有优化，space 用法也将为 O(log n)。
但是如果你得到一个糟糕的 运行 快速排序会怎样？也就是说，如果您总是选择数组中绝对最大或绝对最小的元素作为每个点的轴心点，会发生什么情况？然后你的递归树看起来像这样：
size n
\
size n-1
\
size n-2
\
...
\
1
现在你的递归树的高度为 Θ(n)，因此如果在没有任何尾调用消除的情况下实现，快速排序将使用 Θ(n) space，每个点的每个活动递归调用一个。
我了解到，在没有 Sedgewick 消除尾递归技巧的情况下，快速排序的 space 复杂度为 O(n)。但是，如果我们跟踪存储在堆栈上的调用，就会发现任何调用都是 O(log n) 步，如图所示。
图中，
在计算 (1,1) 的值时，我们存储 [(1,8), (1,4), (1,2)] ,
的调用在计算 (3,3) 的值时，我们存储 [(1,8)、(1,4)、(3,4)] 等的调用
在蚂蚁时间点仅构成 O(log n) space。那么复杂度是不是变成了O(n)？
在您上面给出的树示例中，您展示了一个 运行 的快速排序，它总是恰好在每一步中选择准确的中值元素作为拆分点。这使得递归深度为 O(log n)，因此，如您所述，即使没有优化，space 用法也将为 O(log n)。
但是如果你得到一个糟糕的 运行 快速排序会怎样？也就是说，如果您总是选择数组中绝对最大或绝对最小的元素作为每个点的轴心点，会发生什么情况？然后你的递归树看起来像这样：
size n
\
size n-1
\
size n-2
\
...
\
1
现在你的递归树的高度为 Θ(n)，因此如果在没有任何尾调用消除的情况下实现，快速排序将使用 Θ(n) space，每个点的每个活动递归调用一个。