题目的回答会整理并在gayhub更新
期待在评论区讨论问题
1.2-3
原题：
n的最小值为何值时，运行时间为100n2的一个算法在相同机器上快于运行时间为2n的另一个算法？
回答：
函数图像
函数图像
蓝色的是100n2，绿色的是2n。
第一张是定义域[0,2]的图像。第二张是定义域[0,50]的图像，为了展示效果比例有点扭曲。
从第一张图可以看到，大概n<=0.1(实际大点)的时候，蓝线更优。从第二张图可以看到，大概n>=15(实际更大一点点)时候，同样蓝线更优
所以如果n取整而不为零，那么答案就是n=15。
思考题1
1-1
(运行时间的比较) 假设求解问题的算法需要f(n)毫秒， 对下表中的每个函数f(n)和时间t，确定可以在时间t内求解的问题的最大规模n。
| 1秒钟 | 1分钟 | 1小时 | 1天 | 1月(30天) | 1年(365.24天) | 1世纪 | |
|---|---|---|---|---|---|---|---|
| log2n | 1x10301 | ||||||
| n0.5 | 1x106 | 3.6x109 | 12.96x1012 | 7.46x1015 | 6.74x1018 | 9.95x1020 | 9.95x1024 |
| n | 1x103 | 6x104 | 3.6x106 | 8.64x107 | 2.6x109 | 3.16x1010 | 3.16x1012 |
| nlog2n | 140 | 4895 | 2.04x103 | 3.94x104 | 9.77x105 | 1.05x107 | 8.68x1010 |
| n2 | 31.6 | 244.9 | 1897 | 9295 | 5x104 | 1.78x105 | 1.78x106 |
| n3 | 10 | 39.1 | 153.3 | 442.1 | 1373 | 3160 | 1.474 |
| 2n | 9 | 15 | 21 | 26 | 31 | 34 | 41 |
| n! | 6 | 8 | 9 | 11 | 12 | 13 | 15 |
网友评论