不同排序算法在空间复杂度上的差异 [英] Difference in Space Complexity of different sorting algorithms
问题描述
我试图了解不同排序算法的空间复杂性.
I am trying to understand Space Complexities of different sorting algorithms.
http://bigocheatsheet.com/?goback=.gde_98713_member_241501229
从上面的链接我发现气泡排序，插入和选择排序为O(1)
快速排序为O(log(n))，合并排序为O(n).
http://bigocheatsheet.com/?goback=.gde_98713_member_241501229
from the above link I found that the complexity of
bubble sort,insertion and selection sort is O(1)
where as quick sort is O(log(n)) and merge sort is O(n).
实际上，我们没有在任何算法中分配额外的内存.那么为什么当我们使用相同的数组对它们进行排序时，空间复杂度却有所不同呢?
we were actually not allocating extra memory in any of the algorithms. Then why the space complexities are different when we are using the same array to sort them?
推荐答案
运行代码时，可以通过两种方式分配内存:
When you run code, memory is assigned in two ways:
-
在设置函数调用时，很容易.
Implicitly, as you set up function calls.
明确地，当您创建内存块时.
Explicitly, as you create chunks of memory.
Quicksort是隐式使用内存的一个很好的例子.在进行快速排序时，在最坏的情况下我递归地称自己 O(n)次，在一般情况下是 O(log(n)).这些递归调用各自占用 O(1)空间进行跟踪，从而导致 O(n)最坏的情况和 O(log(n))一般情况.
Quicksort is a good example of implicit use of memory. While I'm doing a quicksort, I'm recursively calling myself O(n) times in the worst case, O(log(n)) in the average case. Those recursive calls each take O(1) space to keep track of, leading to a O(n) worst case and O(log(n)) average case.
Mergesort是显式使用内存的一个很好的例子.我使用了两块排序的数据，创建了一个放置合并的位置，然后从这两个位置合并到该合并中.创建放置合并的位置的是 O(n)数据.
Mergesort is a good example of explicit use of memory. I take two blocks of sorted data, create a place to put the merge, and then merge from those two into that merge. Creating a place to put the merge is O(n) data.
要获取 O(1)内存，您既需要不分配内存，也不要递归调用自己.对于所有冒泡，插入和选择排序都是如此.
To get down to O(1) memory you need to both not assign memory, AND not call yourself recursively. This is true of all of bubble, insertion and selection sorts.
这篇关于不同排序算法在空间复杂度上的差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
