本文へスキップ

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


Since 2016.4.19

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

W−2

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

@ 33秒  A 33分  B 33時間  C 33日  D 33週


類題

R01再 V-2


正解

D


解説

例えば、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週 である。

W−1 目次 W−3