アルゴリズム

質問

アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。

ある問題において、大きさ(データ量)nに対して、アルゴリズムA、B、Cの時間計算量が、それぞれn、n^2(nの2乗)、2^n(2のn乗)であるとする。
(1)アルゴリズムAを用いて10秒間にn=100の問題が解けた。20秒かけるとき扱える問題の大きさnの値を求めよ。
解)
n=100*2
=200

(2)ある計算機を用いてアルゴリズムBで10秒間にn=100の問題が解けた。100倍早い計算機を用いたとき、10秒間に扱える問題の大きさを求めよ。
解)
求める問題の大きさをxとおくと
n=(100^2)*100
=10000*100
=1000000

(3)アルゴリズムCを用いて1時間にn=20の問題が解けた。n=40の問題を解くのに何時間かかるか。
解)
2^40=(2^20)*(2^20)
=1*(2^20)
=2^20[時間]

回答No.2

toshih2000 · ベストアンサー

(1) (3)は正しいと思います。

(2) は
計算量が n^2 なので
100倍速い処理能力の計算機では、nは10倍にしかなりません。
n=100*√100 となります。
100倍速い計算機を使うと言うことは、
同じ計算機で100倍時間を掛けるのと同じです。
100倍時間をかけたら、10000倍の仕事ができた!
こんなすばらしいことは、計算機ではありません。

お礼

回答ありがとうございます。
(2)について、すごく納得できました。

回答No.1

himajin100000

多分考え方はあっていると思う。

ただ、書き方気をつけてね。

2^40=(2^20)*(2^20)
=1*(2^20)

2^40 = 2^20ではないからね

1 * (2^40) /(2^20)
=1 * 2^20
= 2^20[時間]
とか書けば大丈夫かと

お礼

回答ありがとうございます。
確かに、書き方おかしかったです。