本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成18年度 技術士第一次試験問題【専門科目】

W−6

あるアルゴリズムにおいて、データの個数 n について主な操作の実行回数を数えたとき、ほぼ10n + nlog2n 回であった。次のうち最も適切なものを選べ。

@ データが16個のとき200ミリ秒かかるなら、データが64個のときはおよそ910ミリ秒かかる。

A データの個数が200個のときの計算時間は、データの個数が100個のときのほぼ10倍である。

B 1秒でデータの個数が1,000個処理できるとき、2秒で処理できるのはおよそ2,300個までである。

C アルゴリズムの時間計算量はO(n)である。

D アルゴリズムの領域計算量はO(nlog2n)である。


正解

@


解説

@ 正しい。
n = 16個のとき
10×16 + 16×log216 = 160 + 16×4 = 224回
n = 64個のとき
10×64 + 64×log264 = 640 + 64×6 = 1024回
224回で200ミリ秒かかるなら、1024回で914秒かかる。

A n = 100のとき
10×100 + 100×log2100 = 1000+664 = 1664回
n = 200のとき
10×200 + 200×log2200 = 2000+1529 = 3529回
従って、1.12倍である。

B n = 1000のとき
10×1000 + 1000log21000 = 10000+9966 = 19966回
n = 2300のとき
10×2300 + 2300log22300 = 23000+25685 = 48685回
2300個処理するには2.4秒程度かかる。
従って2秒では1900個程度までである。

C アルゴリズムの時間計算量はO(10n + nlog2n) である。割り切ってしまえば、O(n) と言えるが、選択肢の中では、最も適切な答えではない。

D 領域計算量はどれだけメモリが必要かを表す指標である。

W−5 目次 W−7