- ベストアンサー
素数生成 by エラトステネスの篩：多項式時間計算
n*log(log(n)) < n^2 ∈ ｛多項式｝ なのですから、下記ウィキペディアの 「has an exponential time complexity （＝ 指数関数的な時間計算量となる）」という記述は間違って居ますね？： https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
- 木村 弘一（こういち）（@koitiluv1842）
- お礼率92% (25/27)
- その他([技術者向] コンピューター)
- 回答数2
- ありがとう数3
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (1)
- chie65535
- ベストアンサー率43% (8536/19406)
続いてwith regard to input size,とあるように、入力サイズに対して指数関数的な時間計算量となる、のです。 「n未満のすべての素数を計算する時間計算量はO ( n log log n )回の演算」と書いてある通り、計算する時間計算量が「指数関数的な時間計算量」になる、とは書いてありません。 判りやすく簡単に言うと「ｎが巨大になると、篩に使う表が巨大になり、表を初期化する時間が、指数関数的に増えるよ」って言ってるだけです。 例えば、１億までの素数を計算するには、最初に、１億サイズの表を用意し、その表の１枠１枠をTrueに初期化するのを、１億回繰り返さねばなりません。 その「初期化に要する計算時間」が「指数関数的に増加する」って言ってるのです。
補足
御回答の第一段落と第二段落が全く矛盾していますよ。エラトステネスの篩に「表の初期化」など要りませんしね。
関連するQ&A
- 指数積分：閉曲線積分、極、留数
次の積分が解けません。 ∫a→+∞ e^{-t}/t dt …（１） a > 0, a,t:実数 （１）の指数積分は複素積分で解けると教授に言われましたが、さっぱりわかりません。ずっと考えているのですが…助けてください。 http://en.wikipedia.org/wiki/Methods_of_contour_integration http://en.wikipedia.org/wiki/Exponential_integral
- ベストアンサー
- 数学・算数
- 1.なぜ人間には慈悲があるのか？慈悲とはいったいな
1.なぜ人間には慈悲があるのか？慈悲とはいったいなんなのだろうか？ 2.皆さんにとって慈悲とは？ 哲学カテゴリー皆さんの ご回答のほど、 お待ちしております。 https://ja.m.wikipedia.org/wiki/慈悲 https://en.wikipedia.org/wiki/Loving-kindness https://en.wikipedia.org/wiki/Chesed https://en.wikipedia.org/wiki/Mettā
- 締切済み
- 哲学・倫理・宗教学
- ノルウェー、スウェーデン、デンマーク語のそれぞれの
ノルウェー、スウェーデン、デンマーク語のそれぞれのおススメの学習参考書、辞書、読み物とは？ 皆さんにとってノルウェー語、スウェーデン語、デンマーク語とは？ 言語カテゴリー皆さんの ご回答のほど、 お待ちしております。 https://ja.m.wikipedia.org/wiki/デンマーク語 https://ja.m.wikipedia.org/wiki/スウェーデン語 https://ja.m.wikipedia.org/wiki/ノルウェー語 https://en.wikipedia.org/wiki/Danish_language https://en.wikipedia.org/wiki/Swedish_language https://en.wikipedia.org/wiki/Norwegian_language
- 締切済み
- 英語
- Iphoneパソコンをしている現代人を原始古代中世
Iphoneパソコンをしている現代人を原始古代中世近代人が 見たらば何と言うのだろうか？ (シャーマン、魔術師、悪魔使い、アンティクコレクター、 未来から来た人間、 独り言を言う頭が可笑しい人間、 光り輝き言葉を喋り、模様が変わる珍しい石(iphoneパソコン)と会話し遊ぶ人間. 予言者モーゼの十戒見たいなものを持つ人間等々、) Iphone パソコンが発明されてなければ、 我々人類はどのようになっていたのだろうか？ Iphone パソコンの利点、欠点、限界、盲点とは？ 歴史カテゴリー皆さんの ご回答のほど、 お待ちしております。 https://ja.m.wikipedia.org/wiki/IPhone_(初代) https://en.wikipedia.org/wiki/IPhone_(1st_generation) https://ru.wikipedia.org/wiki/IPhone_(первого_поколения) https://ja.m.wikipedia.org/wiki/パーソナルコンピュータ史 https://en.wikipedia.org/wiki/History_of_personal_computers https://ru.wikipedia.org/wiki/История_персональных_компьютеров https://ja.wikipedia.org/wiki/コンピュータ https://en.wikipedia.org/wiki/Computer https://ru.wikipedia.org/wiki/Компьютер https://ja.m.wikipedia.org/wiki/古代 https://en.wikipedia.org/wiki/Ancient_history https://ru.wikipedia.org/wiki/Древний_мир https://ja.wikipedia.org/wiki/世界の歴史 https://es.wikipedia.org/wiki/Historia_universal
- ベストアンサー
- 歴史
- 総鰭類、魚のユーステノプテロンは、水から陸上に？
3億6700万年以上前の デボン紀末期 総鰭類のユーステノプテロンという 一種類の魚だけが、 陸上に上がったのか？ なぜ、 総鰭類(魚)の ユーステノプテロンという 「とんでもない決断」 水から陸上に上がれたのか？ 総鰭類のユーステノプテロンとは、 いったいどんな生き物だったのか？ ユーステノプテロンは、 なぜ、自殺行為に等しい行為を 行えたのか、 ユーステノプテロンの思考に どの様な変化があって、 陸に上がる決断に至ったの？ (どの様な思考の変容で、) 総鰭類は 厳密的には魚に該当するのか？ それとも、魚ではないのか？ 本当に、 エウステノプテロン （異称：ユーステノプテロン 学名：Eusthenopteron）は 四肢動物な祖先なのか？ エウステノプテロンから 浅瀬の泥地に適していた パンデリクティス 陸に上がることができる 肢のような鰭を持った ティクターリク 植物の茂った湿地にいる 初期の四肢動物の例。 八本指の足を持っていた アカントステガ 肢を持っていた イクチオステガ シーラカンスのように 鰭を持った魚もまた子孫に 含まれる。 が派生的に進化誕生したのは 正しいのか、否か？ 社会、生物カテゴリー皆さんの ご回答のほど、 お待ちしております！ 関連 https://ja.m.wikipedia.org/wiki/エウステノプテロン https://en.wikipedia.org/wiki/Eusthenopteron https://ja.m.wikipedia.org/wiki/パンデリクティス https://en.wikipedia.org/wiki/Panderichthys https://ja.m.wikipedia.org/wiki/ティクターリク https://en.wikipedia.org/wiki/Tiktaalik https://ja.m.wikipedia.org/wiki/アカントステガ https://en.wikipedia.org/wiki/Acanthostega https://ja.m.wikipedia.org/wiki/イクチオステガ https://en.wikipedia.org/wiki/Ichthyostega https://ja.m.wikipedia.org/wiki/シーラカンス https://en.wikipedia.org/wiki/Coelacanth
- ベストアンサー
- 生物学
- 1.スイス🇨🇭のローザンヌの観光名所とは？
1.スイス🇨🇭のローザンヌの観光名所とは？ 2.皆さまにとってスイス🇨🇭のローザンヌとは？ 地理カテゴリー皆さまの ご回答のほど、 お待ちしております。 https://ja.m.wikipedia.org/wiki/ローザンヌ https://en.wikipedia.org/wiki/Lausanne https://de.wikipedia.org/wiki/Lausanne 1.Aktivitäten in Lausanne, Schweiz 2.Was ist das Lausanne in der Schweiz? Geographie-Kategorie von Ihnen Wie Sie antworten, Wir warten auf Sie https://en.m.wikipedia.org/wiki/Lausanne https://en.wikipedia.org/wiki/Lausanne https://de.wikipedia.org/wiki/Lausanne
- ベストアンサー
- ヨーロッパ
- シュタゲゼロのbc18000年はクロノトリガへのオ
シュタゲゼロのbc18000年はクロノトリガへのオマジューか何かなのだろうか？ アニメカテゴリー皆さんの ご回答のほど、 お待ちしております。 https://ja.m.wikipedia.org/wiki/クロノ・トリガー https://en.wikipedia.org/wiki/Chrono_Trigger https://en.wikipedia.org/wiki/Steins;Gate_(TV_series)
- 締切済み
- アニメ・声優
- 1.さらざんまいはアダルトチルドレンや毒親がテーマ
1.さらざんまいはアダルトチルドレンや毒親がテーマのアニメなのだろうか？ 2.皆さんにとってさらざんまいとは？ アニメカテゴリー皆さんの ご回答のほど、 お待ちしております。 https://ja.m.wikipedia.org/wiki/アダルトチルドレン https://ja.wikipedia.org/wiki/毒親 https://en.wikipedia.org/wiki/Alcoholism_in_family_systems https://ja.m.wikipedia.org/wiki/さらざんまい https://en.wikipedia.org/wiki/Sarazanmai
- ベストアンサー
- アニメ・声優
- 日本とアメリカの葬式の違いとは？アメリカの葬式で気
日本とアメリカの葬式の違いとは？アメリカの葬式で気をつけることとは？ 人類学カテゴリー皆さんの ご回答のほど、 お待ちしております https://en.wikipedia.org/wiki/Funeral https://ja.wikipedia.org/wiki/葬儀 https://en.m.wikipedia.org/wiki/State_funerals_in_the_United_States
- 締切済み
- 考古学・人類学
- アイスランド語、グリーンランド語のそれぞれのおスス
アイスランド語、グリーンランド語のそれぞれのおススメの学習参考書、辞書、読み物とは？ 皆さんにとってアイスランド語、グリーンランド語とは？ 言語カテゴリー皆さんの ご回答のほど、 お待ちしております。 https://ja.m.wikipedia.org/wiki/アイスランド語 https://en.wikipedia.org/wiki/Icelandic_language https://ja.m.wikipedia.org/wiki/グリーンランド語 https://en.wikipedia.org/wiki/Greenlandic_language
- 締切済み
- 英語
お礼
有難う御座います。有り得ます、という意味ですね？しかし、補足内容を御覧下さい。自明な事を尋ねた、愚問なのでした。
補足
下記の関連 Q&A から、答えがイエスな事は、自明でした。: https://okwave.jp/qa/q10133926.html