performance - Eratosthenes 筛法与试验划分时间复杂度

Question

根据此链接http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

通过试分查找素数列表的时间复杂度为

n*sqrt(n)/ln(n)^2

用埃拉托色尼筛法寻找素数的时间复杂度是

n*ln(ln(x))

论文声称筛法的时间复杂度优于试分法。但是，如果我绘制这些函数，则筛子显然更差:

此图片创建于 WolframAlpha使用查询

PLOT ( n*sqrt(n)/ln(n)^2 / (n*ln(ln(n)) )) from 1 to 100

因此，仅基于大 O 符号，我会得出结论，对于任意大的 n，试验除法应该更好。这个结论正确吗？

但如果我改变常量，结果就会发生变化。似乎没有独立于常数的渐近散度。那么根据大 O 表示法的时间复杂度来断定哪种算法对于任意大的 n 更好似乎是毫无用处的。知道哪个更好的唯一方法是比较实现。 我的结论有误吗？

Answer 1

The paper claims that the sieve has better time complexity than trial division. However, if I plot these functions the sieve is clearly worse. Therefore, based only on big O notation I would conclude that trial division should be better for arbitrarily large n. Is this conclusion correct?

不，结论是错误的，图中没有显示整个图片，因为您需要考虑常量和更大的 n 值的函数行为。

要检查函数 f(n) 是否“渐近优于”函数 g(n)，您需要检查在无穷大处发生了什么。这可以这样做:

lim_{n->infinity} f(n)/g(n)

现在，您有 3 种可能性:

1. limit 是无穷大 -> f(n) 优于 g(n)
2. limit 是一个常数 > 0 -> 函数的行为渐近相似，事实上 f(n) 在 Theta g(n) 中，反之亦然。
3. limit 是 0 - g(n) 优于 f(n)。

From checking your functions on wolfram alpha ，我们可以得出结论，第一个 - n*sqrt(n)/ln(n)^2 在大 O 表示法方面“较慢”。

---

对于 n 的“小”值 - 所有赌注均无效，大 O 表示法对这些情况不提供信息。要针对这些情况做出信息丰富的决策，您需要考虑常量和其他因素(有些与机器相关)。一个可靠的答案不是理论上的，应该通过经验实验和 statistic tests 来实现。 .