0

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

合并排序可以适应在具有 O(1) 额外空间的链表上进行操作。堆排序可以适应在双向链表上进行操作，只需 O(1) 额外的空间开销。

希望能帮助解释这一点（我没有受过计算机科学教育）——尽管我理解上述类型在初级水平上是如何工作的。

4

1 回答 1

3

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

编辑：

一些最常用的符号：

  • O(1) - 常数 - 使用的时间或内存不取决于算法所处理的结构的大小
  • O(n) - 线性 - 取决于结构的大小 - 结构越大 - 需要的时间/内存越多
  • O(logn) -对数 ...

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

于 2013-07-26T08:32:44.730 回答