algorithm - 不同排序算法的空间复杂度差异

Question

我正在尝试了解不同排序算法的空间复杂度。

http://bigocheatsheet.com/?goback=.gde_98713_member_241501229
从上面的链接我发现 冒泡排序、插入排序和选择排序是O(1)
其中快速排序是 O(log(n))，归并排序是 O(n)。

我们实际上并没有在任何算法中分配额外的内存。 那为什么用同一个数组排序，空间复杂度不一样呢？

Answer 1

当您运行代码时，内存以两种方式分配:

1. 隐含地，在您设置函数调用时。

2. 明确地说，当您创建内存块时。

快速排序是隐式使用内存的一个很好的例子。当我进行快速排序时，我在最坏的情况下递归调用自己 O(n) 次，在一般情况下调用 O(log(n)) 次。这些递归调用每个都占用 O(1) 空间来跟踪，导致 O(n) 最坏情况和 O(log(n)) 平均情况。

合并排序是显式使用内存的一个很好的例子。我采用两个已排序数据 block ，创建一个放置合并的位置，然后将这两个数据 block 合并到该合并中。创建放置合并的位置是 O(n) 数据。

要降低到 O(1) 内存，您需要既不分配内存，又不递归调用自己。这适用于所有冒泡排序、插入排序和选择排序。