我在比较堆排序和归并排序时读到下面的语句:
归并排序可以适用于对具有 O(1) 额外空间的链表进行操作。堆排序可以适用于在仅 O(1) 额外空间开销的双向链表上进行操作。
希望能帮助解释这一点(我没有受过计算机科学教育)——尽管我了解上述分类在初级水平上的工作原理。
最佳答案
这是一个 Big O Notation .它用于描述算法的复杂性(时间/内存使用)(查看链接了解更多详情)。这里的意思是，您阅读的算法可以扩展到在提到的情况下工作，并且需要进行的更改将导致需要更多的空间。也就是说，额外的空间不会取决于结构的大小。它将是常量 - 例如，多一个变量。
编辑:
一些最常用的符号:
- O(1) - 常量 - 使用的时间或内存不依赖于算法所处理的结构的大小
- O(n) - 线性 - 取决于结构的大小 - 结构越大 - 需要的时间/内存越多
- O(logn) - logarithmic ...
更多详情请查看here
关于algorithm - 'comparison' 排序比较，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17873250/