アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。
ある問題において、大きさ(データ量)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ベストアンサー
- 回答日時:
(1) (3)は正しいと思います。
(2) は
計算量が n^2 なので
100倍速い処理能力の計算機では、nは10倍にしかなりません。
n=100*√100 となります。
100倍速い計算機を使うと言うことは、
同じ計算機で100倍時間を掛けるのと同じです。
100倍時間をかけたら、10000倍の仕事ができた!
こんなすばらしいことは、計算機ではありません。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
[ EXCEL VBA ] 図形を読み込む...
-
アルゴリズムとプロトコールの違い
-
正しい五十音順について
-
実践的な遺伝子的アルゴリズム...
-
visual basic プログラミング
-
期間重複チェックがわかりません
-
C# 再帰よるスタックオーバー...
-
G4圧縮をTIFに変換アルゴリズム...
-
経路探索について
-
BCDについて
-
検索エンジンペナルティについて
-
複数の点を最短距離で全て繋ぐ...
-
65536は2の何乗なのでしょうか?
-
あるプログラムのコマンドライ...
-
Excelで4096点以上のFFTの方法
-
VBAで仕様書は書きますか?
-
画像を読み込むのと取り込むの...
-
エクセル以外で麻雀の成績を管...
-
変化させるセルが変化しない
-
WORD印刷できるがEXCE...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
SNSをやらない理由ってなんです...
-
アルゴリズムとプロトコールの違い
-
[ EXCEL VBA ] 図形を読み込む...
-
BCDについて
-
期間重複チェックがわかりません
-
最大公約数を求めたい!
-
c言語で画像から文字を認識 キ...
-
C♯で電卓を作成しています。演...
-
多変数関数の最小値を求めるプ...
-
画像から文字を認識してテキス...
-
ハッシュアルゴリズム
-
偏りのある乱数のアルゴリズム
-
乗換案内の作り方が知りたいです。
-
JPEG圧縮で8×8に分割する理由に...
-
書籍のソースコードを別言語に...
-
グループを均等に分けるには?...
-
複数の点を最短距離で全て繋ぐ...
-
gooという検索エンジンの後にGo...
-
シードを考慮したトーナメント...
おすすめ情報