空间差异不同排序算法的复杂性
我想了解不同排序算法的空间复杂性。
http://bigocheatsheet.com/?goback=.gde_98713_member_241501229
从上面的链接我发现，气泡排序，插入和选择排序的复杂性是O（1）
快速排序为O（log（n）），合并排序为O（n）。
我们实际上没有在任何算法中分配额外的内存。 那么为什么当我们使用相同的数组对它们进行排序时，空间复杂性是不同的？
当你运行代码时，内存分配有两种方式：
隐含地，当你设置函数调用。
显然，当你创建大块的内存。
快速排序是隐式使用内存的一个很好的例子。 当我做快速排序时，我在最坏的情况下递归地称自己为O(n)次，在平均情况下为O(log(n)) 。 这些递归调用每个都需要O(1)空间来跟踪，导致O(n)最差情况和O(log(n))平均情况。
Mergesort是显式使用内存的一个很好的例子。 我采用两个已排序数据块，创建一个放置合并的位置，然后将这两个合并到合并中。 创建一个放置合并的地方是O(n)数据。
为了回到O(1)内存，你需要既不分配内存，也不递归地调用你自己。 所有泡沫，插入和选择种类都是如此。
请记住，有很多不同的方法来实现这些算法，并且每个不同的实现都有不同的相关空间复杂性。
我们从合并排序开始。 数组上mergesort的最常见实现是通过分配一个外部缓冲区来执行各个范围的合并。 这需要空间来容纳数组的所有元素，这需要额外的空间Θ（n）。 但是，也可以对每个合并使用就地合并，这意味着您需要的唯一额外空间就是递归调用的堆栈帧的空间，将空间复杂度降低到Θ（log n），但通过大的常数因子增加算法的运行时间。 您也可以使用就地合并来执行自下而上的合并操作，这只需要O（1）个额外的空间但是具有更高的常量因子。
另一方面，如果您要合并排序链接列表，那么空间复杂度将会大不相同。 您可以合并空间O（1）中的链接列表，因为元素本身可以轻松地重新布线。 这意味着合并排序链接列表的空间复杂度为存储递归调用的堆栈帧所需空间的Θ（log n）。
作为另一个例子，我们来看看quicksort。 Quicksort通常不会分配任何外部存储器，但它确实需要使用它的堆栈帧的空间。 如果枢轴始终是阵列的最大或最小元素，那么对于快速排序的天真实现在堆栈帧的最坏情况下可能需要空间Θ（n），因为在那种情况下，您会一直递归调用大小为n的数组上的函数 - 1，n - 2，n - 3等等。但是，您可以执行的标准优化基本上是tail-call消除：您在数组的两半中的较小者上递归调用快速排序，然后重用堆栈空间目前要求较大的一半。 这意味着您只需为最大n / 2，n / 4，n / 8等的子阵列分配新的内存以便递归调用，因此空间使用率将降至O（log n）。
我假设我们排序的数组是通过引用传递的，我假设数组的空间不计入空间复杂度分析。
快速排序的空间复杂度可以通过巧妙的实现进行O(n) （和随机快速排序的预期O(log n) ）：例如，不要复制整个子数组，而只是传递索引。
快速排序的O(n)来自于“嵌套”递归调用的数量可以是O(n)的事实：想想如果您不断对主键做出不幸的选择会发生什么。 虽然每个堆栈帧占用O(1)空间，但可以有O(n)堆栈帧。 如果我们讨论随机快速排序，预期深度（即预期的堆栈空间）为O(log n) 。
对于合并排序，我期望空间复杂度为O(log n)因为您最多可以创建O(log n) “嵌套”递归调用。
您引用的结果还计算了数组占用的空间：然后合并排序的时间复杂度为堆栈空间的O(log n)加上数组的O(n) ，这意味着总空间复杂度为O(n) 。 对于快速排序，它是O(n)+O(n)=O(n) 。
上一篇: Difference in Space Complexity of different sorting algorithms