快速排序的堆栈大小 [英] quicksort stack size

问题描述

为什么我们preFER排序一个文件的小分区，并推进堆栈较大的一个分区后的快速排序（非递归实现）？这样做可以减少快速排序O代表随机文件的空间复杂度（log n）的。可能有人细说吗？

Why do we prefer to sort the smaller partition of a file and push the larger one on stack after partitioning for quicksort(non-recursive implementation)? Doing this reduces the space complexity of quicksort O(log n) for random files. Could someone elaborate it?

推荐答案

如你所知，在每个递归步骤中，您分区阵列。推堆栈上的较大部分，继续工作的较小部分。

As you know, at each recursive step, you partition an array. Push the larger part on the stack, continue working on the smaller part.

由于你坚持下去有工作的一个是较小的一个，它至多是一个你与之前工作的一半大小。因此，对于我们推进栈上的每个范围内，我们一半，我们正在使用的范围的大小。

Because the one you carry on working with is the smaller one, it is at most half the size of the one you were working with before. So for each range we push on the stack, we halve the size of the range we're working with.

这意味着我们不能把超过日志N 的取值范围到范围之前，我们正在与命中尺寸1（并因此排序）堆栈。这种界定堆栈，我们需要完成的第一个下降的数额。

That means we can't push more than log n ranges onto the stack before the range we're working with hits size 1 (and therefore is sorted). This bounds the amount of stack we need to complete the first descent.

当我们开始处理大部件，每个重要组成部分B（k）是大于在同一时间生产的小部分S（k）的，所以我们可能需要更多的堆栈处理B（ k）的比我们需要处理将S（k）。但是，B（k）是仍高于previous小部分小S（K-1），一旦我们正在处理B（K），我们已经采取它从堆栈，因此这是一个项目时相比，我们处理的S（k）的更小，并且大小相同，当我们处理将S（k-1）。所以我们还是有我们的束缚。

When we start processing the "big parts", each "big part" B(k) is bigger than the "small part" S(k) produced at the same time, so we might need more stack to handle B(k) than we needed to handle S(k). But B(k) is still smaller than the previous "small part", S(k-1) and once we're processing B(k), we've taken it back off the stack, which therefore is one item smaller than when we processed S(k), and the same size as when we processed S(k-1). So we still have our bound.

假如我们做到了周围的其他方法 - 推小部分，并继续与大部份的工作。然后在病理讨厌的情况下，我们每次按一个尺寸 1 范围在堆栈上，并继续尺寸只有2比previous尺寸更小的工作。因此，我们就需要 N / 2 插槽，在我们的协议栈。

Suppose we did it the other way around - push the small part and continue working with the large part. Then in the pathologically nasty case, we'd push a size 1 range on the stack each time, and continue working with a size only 2 smaller than the previous size. Hence we'd need n / 2 slots in our stack.

这篇关于快速排序的堆栈大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！