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

Question

我试图了解不同排序算法的空间复杂性.

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

我们实际上并没有在任何算法中分配额外的内存.那么当我们使用相同的数组对它们进行排序时,为什么空间复杂性会有所不同？

Answer 1

运行代码时,内存分配方式有两种:

1. 隐含地,当您设置函数调用时.

2. 明确地,当您创建内存块时.

Quicksort是隐式使用内存的一个很好的例子.虽然我正在做一个快速排序,但O(n)在最糟糕的情况下,我会O(log(n))在一般情况下以递归方式称自己为时间.这些递归调用每个都占用O(1)空间来跟踪,导致O(n)最坏情况和O(log(n))平均情况.

Mergesort是显式使用内存的一个很好的例子.我获取两个排序数据块,创建一个放置合并的位置,然后从这两个合并到该合并.创建放置合并的位置是O(n)数据.

要O(1)记住内存,你既不需要分配内存,也不能递归调用自己.所有泡沫,插入和选择排序都是如此.