algorithm - 这个算法的时间复杂度是多少，它找到每个质数最多为 n

Question

这是有问题的算法，用伪代码表示:

list.add(2)
for (i = 3 to n)
    isPrime=true
    for each (j in list)
        if ((i mod j) = 0)
            isPrime=false
            break
    if (isPrime)
        list.add(i)
return list

今天我的助教告诉我这个算法的复杂度为 O(n^2)，但我很确定这是不正确的，尤其是考虑到任何 n 之前大约有 n/ln(n) 个素数，因此，如果 n 本身是质数，则内部循环在其最后一次迭代中不会迭代超过 n/ln(n) 次。但是我认为它实际上低于 O(n^2/ln(n)) 实际上，但我不确定如何确定它实际上是什么。例如，每个偶数只迭代第二个循环两次。

Answer 1

在您要检查是否为质数的 n 个数中，大约有 n/ln(n) 个实际上是质数，需要所有 i/ln(i) 已经找到可以作为除数的质数。因此，你的算法的复杂度是 W(n^2/ln(n)^2) (W 是 big-omega)和 O(n^ 2/ln(n)。n^2/ln(n)^2 增长速度快于 n * sqrt(n)。

要达到 O(n * sqrt(n)) 时间复杂度，您应该使用以下伪代码:

list.add(2)
for (i = 3 to n)
    isPrime=true
    for each (j in list)
        if j > sqrt(i)
            break
        if ((i mod j) = 0)
            isPrime=false
            break
    if (isPrime)
        list.add(i)
return list