算法导论答题笔记_0x2

题目的回答会整理并在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世纪
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