大多数排序算法的空间复杂度都是O(1)辅助的



我在wiki和其他一些文本中看到,他们说气泡排序、插入排序、选择排序等的空间复杂性是O(1)辅助的。它们是指程序中使用的变量所需的常量存储单元吗。

是的,它们指的是大多数排序都是就地排序,因此它们具有恒定的内存使用率。如果排序不到位,那么它将至少需要O(n)额外的内存。

如果算法在没有任何附加空间或内存的情况下工作,则称为"原位"

http://en.wikipedia.org/wiki/In_situ

如果执行算法所需的额外内存量为O(1),则称算法为原位算法或原位算法

最新更新