平成18年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
W−6
あるアルゴリズムにおいて、データの個数 について主な操作の実行回数を
数えたとき、ほぼ10 + log2 回であった。次のうち最も適切なものを選べ。

 @ データが16個のとき200ミリ秒かかるなら、データが64個のときは
   およそ910ミリ秒かかる。
 A データの個数が200個のときの計算時間は、データの個数が100個の
   ときのほぼ10倍である。
 B 1秒でデータの個数が1,000個処理できるとき、2秒で処理できるのは
   およそ2,300個までである。
 C アルゴリズムの時間計算量はO(n)である。
 D アルゴリズムの領域計算量はO(log2)である。




【正解】 @

@正しい。
 n = 16個のとき
 10×16+16×log216=160+16×4=224回
 n = 64個のとき
 10×64+64×log264=640+64×6=1024回
 224回で200ミリ秒かかるなら、1024回で
914秒かかる。
An = 100のとき
 10×100+100×log2100=1000+664=1664回
 n = 200のとき
 10×200+200×log2200=2000+1529=3529回
 従って、2.12倍である。
Bn = 1000のとき
 10×1000+1000log21000=10000+9966=19966回
 n = 2300のとき
 10×2300+2300log22300=23000+25685=48685回
 2300個処理するには2.4秒程度かかる。
 従って2秒では1900個程度までである。
Cアルゴリズムの時間計算量はO(10 + log2)である。
 究極的には、O(n)と言えるが、選択肢の中では、最も適切な答え
 ではない。
D領域計算量はどれだけメモリが必要かを表す指標である。


EXCELのマクロのご相談なら ファーストマクロ 



W−5 目次 W−7
ファーストマクロ TOPページ