根据此链接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 哪种算法更好似乎是毫无用处的。知道哪一个更好的唯一方法是比较实现。 我是否得出了错误的结论？
最佳答案
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 种可能性:
- 极限为无穷大 -> f(n) 优于 g(n)
- limit 是一个常数 > 0 -> 函数的行为渐近相似，事实上 f(n) 在 Theta g(n) 中，反之亦然。
- 限制为 0 - g(n) 优于 f(n)。
From checking your functions on wolfram alpha ，我们可以得出结论，当涉及到大 O 表示法时，第一个 - n*sqrt(n)/ln(n)^2 是“较慢”的。
对于n的“小”值 - 所有的赌注都被关闭，并且大O符号对于这些情况没有提供信息。要针对这些情况做出明智的决策，您需要考虑常量和其他因素(有些因素取决于机器)。对此的可靠答案不是理论上的，而是应该通过经验实验和 statistic tests 来实现。 .
关于performance - 埃拉托斯特尼筛法与试除时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22858211/