如何计算此素数查找器算法的 T(N)

Question

这个算法找到 N 以下的所有素数

var f = function(n){
    var primes = [2];  //1
    var flag; //1
    for(var i=3; i<n; i+=2){  // ( from 3 to n-1 ) / 2
        flag = true; //1
        var startI = 0; // 1
        for(var y=primes[startI]; y<=Math.sqrt(i); y=primes[++startI]){ // ???
            if(i%y === 0) // 1
                flag = false; // 1
        }
        if(flag) // 1
            primes.push(i); // 1
    }
    return primes; // 1
}

到目前为止我的分析已经完成到第一个循环，我不确定如何处理第二个总和（使用 primes.length 和 Math.sqrt 的总和）。

T(n) = 1 + 1 + sum( ( 1+ 1+ ??weird sum???) , from i = 3 to n -1) / 2 + 1 + 1

我知道如何分析到第二个嵌套循环，我怀疑它是围绕 log(N) 或类似的东西，但我想知道确切的迭代次数..

问题：

如何处理那种使用内存中的数组进行迭代的循环？
如果无法得到准确的数字，我怎样才能得到一个好的近似值？

感谢任何帮助（指向类似案例、书籍等的链接）。

Answer 1

内部循环遍历sqrt(i)以下所有素数的数组。所以你必须计算该数组中元素的数量。在素数数组的情况下，您必须使用 π(i) 的近似值，低于 i 的素数数量。

您可以通过 x/ln(x) 或（更好）通过 li(x). More details here 来近似它们。

对于分析 x/ln(x) 会更容易。

你总共得到（假设n = 2k+1）

T(n) = T(n-2) + O(sqrt(n)/( (1/2)⋅ln(n) )) = O( Σ_{i = 1,...,k} 2⋅sqrt(2⋅i+1)/ln(2⋅i+1) )

你从内部 for 循环得到递归公式，迭代小于 sqrt(n)（近似于 sqrt(n)/( (1/2)⋅ln(n) )）的素数数组，以及你必须做的工作来完成这个远，以T(n-2).

为代表

也许你可以再简化一下。我不想取你的乐趣:)[=27=]

提示：也许您可以使用积分来获得总和的近似值。但是我觉得没有"nice"的写法。

如果你忘记了 1/ln(i) 部分，你可以看到 T(n) ∈ o(n3/2) 和 T(n) ∈ ω(n)。也许你可以做得更好。

如@vib 所述，您可以获得更严格的上限 O(n3/2/ln(n))。但请注意 sqrt(n)/ln(n) 只是小于 sqrt(n) 的素数的近似值。因此，您可以通过更好的近似值获得更好的界限。由于这个近似值不提供 π(n) 的精确值，我们不能说这个算法运行在 Θ(n3/2 /ln(n)).

如何计算此素数查找器算法的 T(N)

How to calculate the T(N) for this primes finder algorithm

algorithm

complexity-theory

big-o