1

这是有问题的算法，伪代码：

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/ln(n) 个素数直到任何 n，所以内部如果 n 本身是素数，则循环在其最后一次迭代中的迭代次数不会超过 n/ln(n) 次。但是我认为它实际上低于 O(n^2/ln(n)) ，但我不确定如何确定它实际上是什么。例如，每个偶数只迭代第二个循环两次。

4

2 回答 2

1

在n您检查的n / ln(n)素数中，实际上大约有素数要求将所有i / ln(i)已找到的素数作为除数进行尝试。因此，您的算法的复杂度是W(n^2 / ln(n)^2)( Wis 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
于 2012-05-03T07:02:51.920 回答
0

复杂度是O((n/log(n))**2)。

你分析如下。您会遇到两组数字，素数和复合数。

您有质O(n/log(n))数，您必须针对所有较小的质数对每个质数进行测试，以获得O(n/log(n))每个质数的工作量，以及总O((n/log(n))**2)工作量。

您有O(n - n/log(n)) = O(n)复合材料，每个复合材料都必须在下面的素数的某个子集上进行测试，以进行以sqrt(n)为界的工作，O(sqrt(n))因此总工作以 为界O(n sqrt(n))。

因此，该O((n/log(n))**2)术语占主导地位。

当然，这不是你的直觉引导你走向的答案。如果您很聪明并在素数平方超过您的目标数时切断内部循环，您试图直觉会发生什么，那么需要多长时间？答案是O(n sqrt(n) / (log(n))**2)。原因是O(sqrt(n)/log(sqrt(n)) = O(sqrt(n)/log(n))下面有素数，每个素数sqrt(n)都需要进行O(n/log(n))数字测试（请参阅http://mathworld.wolfram.com/MertensTheorem.html了解为什么会这样）。

然而，在这一点上，我们已经从算法的世界进入了数论的世界。:D

于 2012-05-03T07:19:55.580 回答