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

今日の私のTAは、このアルゴリズムの複雑さはO（n ^ 2）であると教えてくれましたが、特に任意のnまでの素数が約n / ln（n）であることを考えると、これは正しくないことは間違いありません。 n自体が素数である場合、ループは最後の反復でn / ln（n）回を超えて反復しません。しかし、実際にはO（n ^ 2 / ln（n））よりも低いと思いますが、実際に何であるかを判断する方法がわかりません。たとえば、すべての偶数は2番目のループを2回だけ繰り返します。

4

2 に答える 2

1

素数であることを確認している数の中nには、ほぼn / ln(n)実際に素数があり、i / ln(i)すでに見つかったすべての素数を除数として試す必要があります。したがって、アルゴリズムの複雑さはW(n^2 / ln(n)^2)（Wbig-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)です。

次のように分析します。遭遇する数には、素数と合成の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 に答える