第一章 算法在计算中的作用
1.1
略
1.2
1.2-1
略
1.2-2
$8n^2=64nlgn$ (n为大于1的正整数)
对于[2,43]的n值，插入排序优于归并排序
1.2-3
n最小值为15时，运行时间为$100n^2$的一个算法在相同机器上快于运行时间为$2^n$的另一个算法
章末思考题
1-1
| 1秒钟 | 1分钟 | 1小时 | 1天 | |
|---|---|---|---|---|
| $lgn$ | $2^{1\times10^{3} }$ | $2^{6\times{ {10}^4} }$ | $2^{3.6\times{ {10}^6} }$ | $2^{8.64\times{ {10}^7} }$ |
| $\sqrt{n}$ | $1\times10^{6}$ | $3.6\times10^{9}$ | $1.30\times10^{13}$ | $7.46\times10^{15}$ |
| $n$ | $1\times10^3$ | $6\times10^{4}$ | $3.6\times10^6$ | $8.64\times10^7$ |
| $nlgn$ | $140$ | $4,895$ | $204,094$ | $3,943,234$ |
| $n^2$ | $31$ | $244$ | $1,897$ | $9,295$ |
| $n^3$ | $9$ | $39$ | $153$ | $442$ |
| $2^n$ | $9$ | $15$ | $21$ | $26$ |
| $n!$ | $6$ | $8$ | $9$ | $11$ |
| 1月 | 1年 | 1世纪 | |
|---|---|---|---|
| $lgn$ | $2^{2.59\times{ {10}^9} }$ | $2^{3.11\times{ {10}^{10} } }$ | $2^{3.11\times{ {10}^{12} } }$ |
| $\sqrt{n}$ | $6.72\times10^{18}$ | $9.67\times10^{20}$ | $9.67\times10^{24}$ |
| $n$ | $2.59\times10^9$ | $3.11\times10^{10}$ | $3.11\times10^{12}$ |
| $nlgn$ | $97,659,289$ | $1,038,468,132$ | $85,644,334,437$ |
| $n^2$ | $50,911$ | $176,363$ | $1,763,632$ |
| $n^3$ | $1,373$ | $3,144$ | $14,597$ |
| $2^n$ | $31$ | $34$ | $41$ |
| $n!$ | $12$ | $13$ | $15$ |
注
如无注明，$lg$的底数为2