如何计算算法的空间复杂度

StackOverflow https://stackoverflow.com/questions/3845692

题

我检讨我的数据结构和算法分析教训，我得到如何确定的归并排序和快速排序 算法

  

递归的深度仅为O（LGN），用于链接的列表合并排序

     

需要连续快速排序的的额外的存储空间量为O（n）。

我的想法：

这两个都使用分而治之的策略，所以我想链表归并排序的空间复杂度应该是一样的连续快速sort.Actually我选择了O（LGN），因为每次迭代或递归调用之前，该列表分为一半。

感谢任何指针。

有帮助吗？

解决方案

递归对于快速排序最坏的情况深度不是（一定）O（log n）的，因为快速排序不分割数据“在半”，它分裂它围绕其可以是或可以不是中间的枢轴。它可以实现快速排序来解决这个[*]，但想必O（n）的分析是一个基本的递归快速执行的，而不是一个改进版本。这将占到你在说块引用什么，你“我的想法”在说什么之间的差异。

除此之外，我觉得你的分析是合理的 - 既不算法使用比每递归的水平固定金额以外的任何额外的内存，所以递归使然深度的答案

另一种可能的方式来考虑这种差异，我想是，将O（n）的分析是错误的。或者，“连续的快速排序”是不是我以前听说过的术语，所以如果这并不意味着什么，我认为它（“quicksorting数组”），这可能意味着一个快速排序这是一定的空间，效率低下，在某种意义上如返回一个分配的阵列，而不是就地排序。但是，这将是愚蠢的快速排序和归并比较的输入为快速排序的副本归并对大小的递归深度的基础上。

[*]具体而言，代替递归调用该函数在两个部分，你把它放在一个循环。就在小部分递归调用，并循环周围做更大的一部分，或者等价地推（指向）较大的部分到工作组之后做的，和周围循环做小部分。无论哪种方式，您可以确保堆栈的深度不会超过数N，因为工作的每个块的不的放在堆栈中是最多的块大小的一半之前，下降到一个固定的最小（1或2，如果你纯粹与快速排序排序）。

其他提示

我不是很熟悉的术语“连续的快速排序”。不过，快速排序可以根据它是如何实现要么为O（n）或O（log n）的空间复杂度。

如果它是这样实现的：

quicksort(start,stop) {
    m=partition(start,stop);
    quicksort(start,m-1);
    quicksort(m+1,stop);
}

然后，将空间复杂度为的 O（n）的下，不O（log n）的作为通常认为。 这是因为你在每个水平推送到堆栈上的两倍，因此空间复杂度从复发时确定：

T(n) = 2*T(n/2)

假设分区划分阵列分为两个等份（最好情况）。根据主定理是T（N）= O（n）中。向此溶液中

如果我们替换尾递归第二快速排序呼叫在上面的代码片断，则得到T（N）= T（N / 2），因此T（N）= O（log n）的（通过的情况下，2主定理）。

也许“连续的快速排序”指的是第一实施，因为这两个快速排序调用是彼此相邻，在这种情况下，空间复杂度为的 O（n）的

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top