算法导论-思考题1-1
1-1（运行时间的比较）假设求解问题的算法需要 $f(n)$微秒(microseconds)，对下表中每个函数$f(n)$和时间$t$可以确定在时间$t$内求解问题的最大规模$n$。
中文版给的$f(n)$单位是毫秒，但看了原版，发现单位是微秒(microseconds)，故下面采用微秒来计算。
| 函数\时间 | 1秒钟 | 1分钟 | 1小时 | 1天 | 1月 | 1年 | 1世纪 |
|---|---|---|---|---|---|---|---|
| $lgn$ | $2^{10^6}$ | $2^{6\times 10^7}$ | $2^{3.6 \times 10^9}$ | $2^{8.64 \times 10^{10}}$ | $2^{2.592 \times 10^{12}}$ | $2^{3.1536 \times 10^{13}}$ | $2^{3.1536 \times 10^{15}}$ |
| $\sqrt n$ | $10^{12}$ | $3.6 \times 10^{15}$ | $1.296 \times10^{19}$ | $7.465 \times 10^{21}$ | $6.718 \times 10^{24}$ | $9.945 \times 10^{26}$ | $9.945 \times 10^{30}$ |
| $n$ | $10^6$ | $6 \times 10^7$ | $3.6 \times 10^9$ | $8.64 \times 10^{10}$ | $2.592 \times 10^{12}$ | $3.1536 \times 10^{13}$ | $3.1536 \times 10^{15}$ |
| $nlgn$ | $62746$ | $2.8 \times 10^6$ | $1.3 \times 10^8$ | $2.7 \times 10^9$ | $7.1 \times 10^{10}$ | $7.9 \times 10^{11}$ | $6.8 \times 10^{13}$ |
| $n^2$ | $1000$ | $7745$ | $60000$ | $293938$ | $1609968$ | $5615692$ | $56175382$ |
| $n^3$ | $100$ | $391$ | $1532$ | $4420$ | $13736$ | $31593$ | $146677$ |
| $2^n$ | $19$ | $25$ | $31$ | $36$ | $41$ | $44$ | $51$ |
| $n!$ | $9$ | $11$ | $12$ | $13$ | $15$ | $16$ | $17$ |
$1s=10^6us$
$1min=6 \times 10^7us$
$1h=3.6 \times 10^9us$
$1D=8.64 \times 10^{10}us$
$1Mon=2.592 \times 10^{12}us$ （1个月30天）
$1Y=3.1536 \times 10^{13}us$ （365天）
$1C=3.1536 \times 10^{15}us$