から




専門/H18/06

正解 Edit

1

検証 Edit

  1. データの個数が16個のとき200ミリ秒かかるなら,データの個数が64個のときはおよそ910ミリ秒かかる。
    • 10n+nlog2n回を計算する。
      16個のとき:10 x 16 + 16log216 = 160 + 16 x 4 = 160 + 64 = 224
      64個のとき:10 x 64 + 64log264 = 640 + 64 x 6 = 640 + 384 = 1024
    • 比率で検証する。 224:200 = 1024:t t= 914
  2. データの個数が200個のとき計算時間は,データの個数が100個のときのほぼ10倍である。
    • 10n+nlog2n回を計算する。
      200個のとき:10 x 200 + 200log2200 = 2000 + 200 (log10200 / log102) = 2000 + 200 (2.3 / 0.3) = 3533
      100個のとき:10 x 100 + 100log2100 = 1000 + 100 (log10100 / log102) = 1000 + 100 (2 / 0.3) = 1667
    • 比率は3533/1667で約2.1倍
  3. 1秒でデータの個数が1,000個処理できるとき,2秒で処理できるのはおよそ2,300個までである。
    • 10n+nlog2n回を計算する。
      1000個のとき:10 x 1000 + 1000log21000 = 10000 + 1000 (log101000 / log102) = 10000 + 1000 (3 / 0.3) = 20000
      2300個のとき:10 x 2300 + 2300log22300 = 23000 + 2300 (log102300 / log102) = 23000 + 2300 (3.3 / 0.3) = 48300
    • 比率より48300/20000 で 約2.4秒かかる。
  4. アルゴリズムの時間計算量はO(n)である。
  5. アルゴリズムの時間計算量はO(nlog2n)である。
  • アルゴリズムの時間計算量はO(10n+nlog2n)ということ?(良く分からんが)

Tag: アルゴリズムの計算量



トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 下位頁新規  一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-22 Mon 23:18:58 JST (3162d)