通用数域筛的速度

Question

因此，根据维基百科页面https://en.wikipedia.org/wiki/General_数_字段_筛，筛，算法具有复杂性\exp \left( \left(\sqrt[\leftroot{1}\uproot{0}3]{\frac{64}{9}} + o(1) \right) (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}} \right)，但我对这个表示法并不太熟悉。

我理解大O符号的复杂性，如果有人能解释这是如何相似的，它对运行时间意味着什么，我们将不胜感激！！

此外，我知道这是n运行时间的次指数，但我不知道如何从这个复杂性来说明这一点。

Answer 1

这是增长曲线的期望值，在算法中的步骤数因子n，或渐近预期运行时间。o(1)项是指以n \to \infty形式收敛到零的函数。这里，“步骤”是算法中循环的次数；每个“步骤”对应一个未指定的(例如)位操作数，我们不考虑存储或通信成本。有关更详细的领域*时间成本分析，请参见，例如，批次NFS纸。