quicksort堆栈大小

quicksort堆栈大小

如您所知，在每个递归步骤中，您都要对数组进行分区。将较大的部分推入堆栈，然后继续处理较小的部分。

因为您要处理的是较小的，所以它最多是以前处理的一半。因此，对于我们推入堆栈的每个范围，我们将所使用范围的大小减半。

这意味着

log n

在我们使用匹配大小为1（因此已排序）的范围之前，我们不能将超出范围的内容压入堆栈。这限制了我们完成第一次下降所需的堆栈数量。

当我们开始处理“大零件”时，每个“大零件” B（k）大于同时生产的“小零件”
S（k），因此，我们可能需要更多的堆栈来处理B（k），而不是我们需要处理S（k）。但是B（k）仍然小于先前的“小部分”
S（k-1），一旦我们处理了B（k）， 我们就将其从堆栈中取出
，因此比其小一号。当我们处理S（k）时，其大小与处理S（k-1）时的大小相同。因此，我们仍然有约束。

假设我们以相反的方式进行了 *** 作-
推动较小的部分并继续处理较大的部分。然后，在病理上令人讨厌的情况下，我们

1

每次都会将大小范围推入堆栈，并继续以仅比先前大小小2的大小工作。因此，我们需要

n/ 2

在堆栈中放置插槽。