2020年10月02日

令和元年度 技術士第一次試験問題(再) 情報工学部門 V−2

V−2

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

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





正解

@


解説

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

タグ:時間計算量
posted by ファーストマクロ at 20:55| Comment(0) | R01技術士一次試験[再](情報工学)
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。