"ln ln n/ ln 2+ O(1)“中的O(1)是什么意思？

Question

我很难理解这个公式中的O(1)符号，它代表一个常数吗？为什么人们会使用像这样的大O符号？

​

​

这个公式来自论文"Balanced Allocations" by Azar et al.，并且这个公式在摘要中使用：

​

​

Answer 1

是的，O(1)表示常量。常量的精确值并未指定，但对于给定的表达式可能并不重要。这些概念通常用作计算中的中间步骤，并且它删除了不重要的细节的计算。

按如下方式阅读此表达式:通过一些常量加法，执行将占用lnlnn/ln2时间。在O(lnlnn)中汇总这一结果。用精确表达式替换O(1)不会改变这个结果，所以以O(1)的形式使用近似值是可以的。