c++ - 二次筛 - o(1) 代表什么？

Question

我正在尝试实现二次筛，我注意到我需要选择一个平滑界 B 来使用这个算法。我在网上发现 B 也代表 exp((1/2 + o(1))(log n log log n)^(1/2)) 但现在我的问题是 o(1)。你能告诉我 o(1) 代表什么吗？

Answer 1

让我们从你的答案开始：

f(n)为o(1)的定义是limn→∞f(n)=0。这意味着对于所有 ϵ>0 存在 Nϵ，取决于 ϵ，因此对于所有 n≥Nϵ 我们有 |f(n)|≤ϵ。

或者用简单的英语：

符号 o(1) 表示“收敛到 0 的函数”。

这是一个很棒的资源：http ://bigocheatsheet.com

查看渐近增长部分的符号

答案也可以在这个重复的帖子中找到：Big-O 和 Little-O Notation 之间的区别

f ∈ O(g) 说，本质上

对于常数 k > 0的至少一个选择，您可以找到一个常数 a，使得不等式 f(x) < kg(x) 对于所有 x > a 都成立。

请注意，O(g) 是该条件成立的所有函数的集合。

f ∈ o(g) 说，本质上

对于常数 k > 0 的每一个选择，您都可以找到一个常数 a，使得不等式 f(x) < kg(x) 对于所有 x > a 都成立。

Answer 2

O(1) 意味着它需要恒定的时间，不受输入大小的影响。o(1)（略有不同！）表示它所代表的函数收敛到 0。我不会太担心平滑度界限，先编写其余更复杂的算法，使用非常简单的平滑度公式。（前 100,000 个素数，或前 n 个素数，其中 n = c *log(number)）一旦算法的其余部分正常工作（并且可能已优化？）然后仔细选择平滑界限实际上会产生显着影响。您在问题中给出的那个冗长的复杂公式是二次筛算法本身的近似（渐近）运行时间，我很确定它与选择平滑度界限无关。