不同排序算法的复杂度差异 Space
Difference in Space Complexity of different sorting algorithms
我正在尝试了解 Space 不同排序算法的复杂性。
http://bigocheatsheet.com/?goback=.gde_98713_member_241501229
从上面link我发现
冒泡排序、插入排序和选择排序是 O(1)
其中快速排序是 O(log(n))，合并排序是 O(n)。
我们实际上并没有在任何算法中分配额外的内存。
那为什么我们使用相同的数组对它们进行排序时 space 复杂度不同？
我假设我们正在排序的数组是通过引用传递的，并且我假设数组的 space 不计入 space 复杂性分析。
快速排序的 space 复杂度可以通过巧妙的实现达到 O(n)（随机快速排序的预期 O(log n)）：例如不要复制整个子数组，而只是传递索引。
快速排序的 O(n) 来自 "nested" 递归调用的 数量 可以是 O(n) 的事实：想想会发生什么如果你一直在为支点做出不幸的选择。虽然每个堆栈帧需要 O(1) space，但可以有 O(n) 个堆栈帧。如果我们谈论的是随机快速排序，预期深度（即预期堆栈space）是O(log n)。
对于合并排序，我预计 space 复杂度为 O(log n)，因为您最多进行 O(log n) "nested" 次递归调用。
您引用的结果还计算了数组所采用的 space：那么合并排序的时间复杂度是 O(log n) 堆栈 space 加上 O(n)对于数组，这意味着 O(n) 总 space 复杂度。对于快速排序，它是 O(n)+O(n)=O(n).
当你运行编码时，内存分配有两种方式：
隐式设置函数调用。
明确地说，当您创建内存块时。
快速排序是隐式使用内存的一个很好的例子。当我进行快速排序时，我在最坏的情况下递归调用自己 O(n) 次，在平均情况下调用 O(log(n)) 次。这些递归调用每个都需要 O(1) space 来跟踪，导致 O(n) 最坏情况和 O(log(n)) 平均情况。
Mergesort 是显式使用内存的一个很好的例子。我采用两个已排序数据块，创建一个放置合并的位置，然后将这两个数据块合并到该合并中。创建放置合并的地方是O(n)数据。
要获得 O(1) 内存，您需要既不分配内存，也不递归调用自己。所有冒泡、插入和选择排序都是如此。
重要的是要记住，有很多不同的方法可以实现这些算法中的每一个，并且每个不同的实现都有不同的相关 space 复杂性。
让我们从合并排序开始。数组上最常见的合并排序实现是通过分配一个外部缓冲区来执行各个范围的合并。这需要 space 来容纳数组的所有元素，这需要额外的 space Θ(n)。但是，您也可以为每次合并使用就地合并，这意味着您唯一需要的额外 space 是递归调用堆栈帧的 space，删除 space 复杂度下降到 Θ(log n)，但算法的运行时间增加了一个很大的常数因子。您也可以使用就地合并进行自下而上的合并排序，这只需要额外的 O(1) space 但具有更高的常数因子。
另一方面，如果您对链表进行合并排序，那么 space 的复杂性将大不相同。您可以在 space O(1) 中合并链表，因为元素本身可以很容易地重新连接。这意味着 space 合并排序链表的复杂度是 Θ(log n) 来自 space 需要存储递归调用的堆栈帧。
让我们以快速排序为例。 Quicksort 通常不分配任何外部内存，但它确实需要 space 用于它使用的堆栈帧。如果枢轴总是最终成为数组的最大或最小元素，那么在堆栈帧的最坏情况下，快速排序的简单实现可能需要 space Θ(n)，因为在这种情况下，您会不断递归调用函数大小为 n - 1、n - 2、n - 3 等的数组。但是，您可以执行一个标准优化，它本质上是尾调用消除：您递归地对数组的两半中较小的一个调用快速排序，然后重用来自当前调用的较大一半的堆栈 space。这意味着您只为递归调用分配新内存，子数组的大小最多为 n / 2，然后是 n / 4，然后是 n / 8，等等，因此 space 的使用率下降到 O(log n)。
我正在尝试了解 Space 不同排序算法的复杂性。
http://bigocheatsheet.com/?goback=.gde_98713_member_241501229
从上面link我发现
冒泡排序、插入排序和选择排序是 O(1)
其中快速排序是 O(log(n))，合并排序是 O(n)。
我们实际上并没有在任何算法中分配额外的内存。 那为什么我们使用相同的数组对它们进行排序时 space 复杂度不同？
我假设我们正在排序的数组是通过引用传递的，并且我假设数组的 space 不计入 space 复杂性分析。
快速排序的 space 复杂度可以通过巧妙的实现达到 O(n)（随机快速排序的预期 O(log n)）：例如不要复制整个子数组，而只是传递索引。
快速排序的 O(n) 来自 "nested" 递归调用的 数量 可以是 O(n) 的事实：想想会发生什么如果你一直在为支点做出不幸的选择。虽然每个堆栈帧需要 O(1) space，但可以有 O(n) 个堆栈帧。如果我们谈论的是随机快速排序，预期深度（即预期堆栈space）是O(log n)。
对于合并排序，我预计 space 复杂度为 O(log n)，因为您最多进行 O(log n) "nested" 次递归调用。
您引用的结果还计算了数组所采用的 space：那么合并排序的时间复杂度是 O(log n) 堆栈 space 加上 O(n)对于数组，这意味着 O(n) 总 space 复杂度。对于快速排序，它是 O(n)+O(n)=O(n).
当你运行编码时，内存分配有两种方式：
隐式设置函数调用。
明确地说，当您创建内存块时。
快速排序是隐式使用内存的一个很好的例子。当我进行快速排序时，我在最坏的情况下递归调用自己 O(n) 次，在平均情况下调用 O(log(n)) 次。这些递归调用每个都需要 O(1) space 来跟踪，导致 O(n) 最坏情况和 O(log(n)) 平均情况。
Mergesort 是显式使用内存的一个很好的例子。我采用两个已排序数据块，创建一个放置合并的位置，然后将这两个数据块合并到该合并中。创建放置合并的地方是O(n)数据。
要获得 O(1) 内存，您需要既不分配内存，也不递归调用自己。所有冒泡、插入和选择排序都是如此。
重要的是要记住，有很多不同的方法可以实现这些算法中的每一个，并且每个不同的实现都有不同的相关 space 复杂性。
让我们从合并排序开始。数组上最常见的合并排序实现是通过分配一个外部缓冲区来执行各个范围的合并。这需要 space 来容纳数组的所有元素，这需要额外的 space Θ(n)。但是，您也可以为每次合并使用就地合并，这意味着您唯一需要的额外 space 是递归调用堆栈帧的 space，删除 space 复杂度下降到 Θ(log n)，但算法的运行时间增加了一个很大的常数因子。您也可以使用就地合并进行自下而上的合并排序，这只需要额外的 O(1) space 但具有更高的常数因子。
另一方面，如果您对链表进行合并排序，那么 space 的复杂性将大不相同。您可以在 space O(1) 中合并链表，因为元素本身可以很容易地重新连接。这意味着 space 合并排序链表的复杂度是 Θ(log n) 来自 space 需要存储递归调用的堆栈帧。
让我们以快速排序为例。 Quicksort 通常不分配任何外部内存，但它确实需要 space 用于它使用的堆栈帧。如果枢轴总是最终成为数组的最大或最小元素，那么在堆栈帧的最坏情况下，快速排序的简单实现可能需要 space Θ(n)，因为在这种情况下，您会不断递归调用函数大小为 n - 1、n - 2、n - 3 等的数组。但是，您可以执行一个标准优化，它本质上是尾调用消除：您递归地对数组的两半中较小的一个调用快速排序，然后重用来自当前调用的较大一半的堆栈 space。这意味着您只为递归调用分配新内存，子数组的大小最多为 n / 2，然后是 n / 4，然后是 n / 8，等等，因此 space 的使用率下降到 O(log n)。