Ｏ(n!) の時間計算量をもつアルゴリズムを、n = 4のとき1秒で計算できるコンピュータがあったとする。問題のサイズが3倍 (n = 12) になったとき、必要な計算時間の見積りとして最も適切なものはどれか。
① 33週 ② 24日 ③ 12時間 ④ 6秒 ⑤ 3秒
①
例えば、Ｏ(2n) は Ｏ(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 ÷ 24 ＝ 19,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週 である。
| Ⅲ－１ | 目次 | Ⅲ－３ |