我很难理解这个公式中的 O(1) 符号，它代表一个常数吗？为什么人们会使用这样的大 O 表示法？
这个公式来自Azar 等人的论文“Balanced Allocations”。，并且在摘要中使用了这个公式：
问问题
1240 次
2 回答
4
在这里，术语 O(1) 的意思是“某项是 O(1)”，这意味着当 n 趋于无穷大时，某个项从上方受到某个常数的限制。例如，它可能是 137、sin n 或 1 / n 2。因此，描述的值可能是 ln ln n / ln 2 + 137，或 ln ln n / ln 2 + sin n 等。
当在公式中讨论对总体总数贡献很小的低阶项时，这种大 O 符号的使用在形式数学中很常见。作者也可以写出整个表达式为 O(ln ln n)，但这不如 ln ln n / ln 2 + O(1) 精确，因为它掩盖了 ln ln n 的系数为 1 的事实/ ln 2 并且唯一的低阶增长项由一个常数限制。通过明确写出“+ O(1)”，作者能够给出更好的精度。
希望这可以帮助！
于 2013-05-08T17:41:39.160 回答
0
是的，O(1)意味着恒定。未指定常量的确切值，但对于给定的表达式可能并不重要。这些概念通常用作计算中的中间步骤，它消除了对不重要细节的计算。
请按如下方式阅读此表达式：执行需要lnlnn/ln2一些持续时间加法。将其总结为O(lnlnn). 用精确表达式替换O(1)不会改变这个结果，所以可以使用O(1).
于 2013-05-08T16:46:36.997 回答