本文へスキップ

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


Since 2016.4.19

令和元年度 技術士第一次試験問題(再)【専門科目】

V−2

O(n!) の時間計算量をもつアルゴリズムを、n = 4のとき1秒で計算できるコンピュータがあったとする。問題のサイズが3倍 (n = 12) になったとき、必要な計算時間の見積りとして最も適切なものはどれか。

@ 33週  A 24日  B 12時間  C 6秒  D 3秒


類題

H24 W-2


正解

@


解説

例えば、O(2n) は O(n)の2倍の時間計算量である。
これを踏まえると、O(12!) は、O(4!) の何倍かが判ればよい。

4!24
12! = 479,001,600
O(12!) = O(12 ×11 × ・・・ × 6 × 5 × 4!)
であり、
12! ÷ 4! = 479,001,600 ÷ 2419,958,400 だから

O(12!) = O(12! ÷ 4! × 4!) = O(19,958,400 × 4!)
よって、O(12!) は、O(4!) の19,958,400倍である。

n = 4のとき1秒で計算できるので、n = 12の時は、
19,958,400秒 = 55,44時間 = 231日 = 33週 である。

V−1 目次 V−3