algorithm - 如何计算此素数查找器算法的 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) .更多 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) 表示.

也许你可以进一步简化这个。我不想从你这里取乐:)

提示:也许您可以使用积分来获得总和的近似值。但我认为没有“好”的方式来写下来。

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

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