Ste*_*sop 11
如您所知,在每个递归步骤中,您都会对数组进行分区.将较大的部件推到堆叠上,继续在较小的部件上工作.
因为你携带的那个是较小的一个,它至多是你之前工作的一半.因此,对于我们推动堆叠的每个范围,我们将我们正在使用的范围的大小减半.
这意味着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堆栈中的插槽.