本記事の概要
第一回の記事を参照ください。
さっそく回答していきます。
（第一回の記事でも申し上げましたが、私の回答は正解ではないですし、間違ってる可能性大！です。）
章末問題1
1-1
以下の表の各関数$f(n)$と時間$t$に対して、アルゴリズムが問題を解くのに$f(n)$マイクロ秒かかるとき、$t$時間でとくことができる最大の問題サイズ$n$を求めよ。
$\log n$合ってないかも…
天文学的過ぎる…
2分探索ってソートされてるデータであればどんなに大きくても現実的な時間で探索が可能ってことなんですかね。
| 1秒 | 1分 | 1時間 | 1日数 | 1月数 | 1年数 | 1世紀 | |
|---|---|---|---|---|---|---|---|
| $\log_2 n$ | $1.0 \times 10^{301000}$ | $1.0 \times 10^{1806000}$ | $1.0 \times 10^{108360000}$ | $1.0 \times 10^{2600640000}$ | $1.0 \times 10^{78019200000}$ | $1.0 \times 10^{949233600000}$ | $1.0 \times 10^{949233600000}$ |
| $\sqrt{n}$ | $1.0 \times 10^{12}$ | $3.6 \times 10^{15}$ | $1.296 \times 10^{16}$ | $7.465 \times 10^{21}$ | $6.718 \times 10^{24}$ | $9.941 \times 10^{26}$ | $9.941 \times 10^{30}$ |
| $n$ | $1000000$ | $6.0 \times 10^7$ | $3.6 \times 10^9$ | $8.64 \times 10^{10}$ | $2.592 \times 10^{12}$ | $3.153 \times 10^{13}$ | $3.153 \times 10^{15}$ |
| $n\log_2 n$ | $62764$ | $2801417$ | $1.333\times10^8$ | $2.755 \times 10^9$ | $7.187 \times 10^{10}$ | $7.976 \times 10^{11}$ | $6.861 \times 10^{12}$ |
| $n^2$ | $1000$ | $7745$ | $60000$ | $293928$ | $1609968$ | $5615692$ | $56156922$ |
| $n^3$ | $100$ | $391$ | $1532$ | $4420$ | $13736$ | $31593$ | $146645$ |
| $2^n$ | $19$ | $25$ | $31$ | $36$ | $41$ | $44$ | $51$ |
| $n!$ | $9$ | $11$ | $12$ | $13$ | $15$ | $16$ | $17$ |
次回
実際のアルゴリズムのコストについて解析していきます。