比较“比较”排序

Question

在比较堆排序和合并排序时，我读到了以下语句：

合并排序可以适用于对具有O(1)额外空间的链表进行操作。堆排序适用于操作双向链表，额外空间开销仅为O(1)。

我希望能帮助解释这一点(我没有受过计算机科学教育)-尽管我理解上面的排序在初级水平上是如何工作的。

Answer 1

这是一个Big O Notation。它用于描述算法的复杂性(时间/内存使用)(更多详细信息，请查看链接)。这里的意思是，您读到的算法可以扩展到在上述情况下工作，并且需要进行的更改将导致恒定-需要更多的空间。也就是说，额外的空间不会取决于结构的大小。它将是常量-例如，多一个变量。

编辑：

一些最常用的符号：

• O(1) - constant -使用的时间或内存不取决于算法在
• 上工作的结构大小O(N)-
• O(N)-取决于结构的大小-结构越大-时间/内存越多- logarithmic ...

有关更多详细信息，请查看here