素数生成 by エラトステネスの篩：多項式時間計算

質問

n*log(log(n)) < n^2 ∈ ｛多項式｝
なのですから、下記ウィキペディアの 「has an exponential time complexity （＝　指数関数的な時間計算量となる）」という記述は間違って居ますね？：
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

回答No.2

mohicans · ベストアンサー

可能です！

お礼

有難う御座います。有り得ます、という意味ですね？しかし、補足内容を御覧下さい。自明な事を尋ねた、愚問なのでした。

補足

下記の関連 Q&A から、答えがイエスな事は、自明でした。:
https://okwave.jp/qa/q10133926.html

回答No.1

chie65536（@chie65535）

続いてwith regard to input size,とあるように、入力サイズに対して指数関数的な時間計算量となる、のです。

「n未満のすべての素数を計算する時間計算量はO ( n log log n )回の演算」と書いてある通り、計算する時間計算量が「指数関数的な時間計算量」になる、とは書いてありません。

判りやすく簡単に言うと「ｎが巨大になると、篩に使う表が巨大になり、表を初期化する時間が、指数関数的に増えるよ」って言ってるだけです。

例えば、１億までの素数を計算するには、最初に、１億サイズの表を用意し、その表の１枠１枠をTrueに初期化するのを、１億回繰り返さねばなりません。

その「初期化に要する計算時間」が「指数関数的に増加する」って言ってるのです。

補足

御回答の第一段落と第二段落が全く矛盾していますよ。エラトステネスの篩に「表の初期化」など要りませんしね。