算法导论答题笔记_0x2

御史神风 · 简书 · · 2018-10-02 21:18

题目的回答会整理并在gayhub更新
期待在评论区讨论问题

1.2-3
原题：
n的最小值为何值时，运行时间为100n²的一个算法在相同机器上快于运行时间为2ⁿ的另一个算法？
回答：

函数图像

蓝色的是100n²，绿色的是2ⁿ。
第一张是定义域[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世纪
log₂n	1x10³⁰¹
n^0.5	1x10⁶	3.6x10⁹	12.96x10¹²	7.46x10¹⁵	6.74x10¹⁸	9.95x10²⁰	9.95x10²⁴
n	1x10³	6x10⁴	3.6x10⁶	8.64x10⁷	2.6x10⁹	3.16x10¹⁰	3.16x10¹²
nlog²n	140	4895	2.04x10³	3.94x10⁴	9.77x10⁵	1.05x10⁷	8.68x10¹⁰
n²	31.6	244.9	1897	9295	5x10⁴	1.78x10⁵	1.78x10⁶
n³	10	39.1	153.3	442.1	1373	3160	1.47⁴
2ⁿ	9	15	21	26	31	34	41
n!	6	8	9	11	12	13	15