[解決済み] エラトステネスの篩アルゴリズムの時間複雑性

質問

から ウィキペディア

このアルゴリズムの複雑さは O(n(logn)(loglogn)) ビット演算です。

どのようにしてそれを実現するのですか？

複雑さには loglogn 項があることを教えてくれます。 sqrt(n) がどこかにあると教えてくれます。

最初の100個の数字に対してふるいを実行するとします ( n = 100 )、数字を合成とマークするのに一定の時間がかかると仮定すると(配列の実装)、何回目に mark_composite() を使用する回数は次のようになります。

n/2 + n/3 + n/5 + n/7 + ... + n/97        =      O(n^2)                         

また、次の素数を見つけるために（例えば、次の素数にジャンプするために 7 の倍数である数字をすべて消去してから 5 の倍数をすべて消すと）、操作の回数は O(n) .

つまり、複雑さは O(n^3) . ということになるのでしょうか？

どのように解決するのですか？

1. あなたのn/2 + n/3 + n/5 + ... n/97は、項数が一定ではないので、O(n)ではありません。[Edit after your edit: O(n) ² ) は緩すぎる上限です] 。緩い上限は n(1+1/2+1/3+1/4+1/5+1/6+...1/n) (sum of reciprocals of the すべての の逆数の和）であり、これは O(n log n) です。 調和数 . より適切な上限は n(1/2 + 1/3 + 1/5 + 1/7 + ...) で、これは n までの素数の逆数の和であり、O(n log log n)です。(参照 を参照。 または ここで .)

2. "次の素数を見つける"ビットは全体でO(n)しかありません。 償却済み - でn回だけ次の数を見つけるために先に進みます。 合計 で、ステップごとではありません。つまり、アルゴリズムのこの部分全体はO(n)しかかからないのです。

つまり、この2つを使うと、O(n log log n) + O(n) = O(n log log n) という算術演算の上界が得られます。ビット演算をカウントすると、n までの数を扱うので、約 log n ビットとなり、ここで log n の因数が入るので、O(n log n log log n) ビット演算が得られます。