算法导论第一章 习题

10 Mar 2013 by LelouchHe

1.1-1

排序: 微博搜索结果中需要综合考量各种因素,比如时间,质量,社会化关系等,此时就是排序操作

凸包: 修建牧场围栏,知道牧场中的点,需要确定牧场围栏的长度,此时计算的就是凸包

1.1-2

考量效率的手段有很多,最为重要的就是时间和空间,即算法执行需要的时间和占用的内存

其他的因素包括编译效率,测试成本(验证是否正确的代价,这个感觉不像..囧..)

1.1-3

红黑树

优点: 非常平衡,在各种情况下的效率基本可以维持不变

缺点: 编程复杂度很大,而且执行效率有所欠缺(比直接的随机数组来说,cache/内存使用较为零散和庞大)

1.1-4

相同点: 二者都是以距离为衡量标准,试图找到”最短”的算法

不同点: 最短路径一般是单向的(双向的其实再翻回来即可),而且对经过的节点没有要求(只要求最短),旅行商问题则在最毒啊你的基础上,要求必须经过所有的点(否则有些节点无法投递了),就是这样一个前提条件,使得旅行商问题成为了NP问题

1.1-5

最优解和次优解在实际工程中都是可以接受的,比如线性规划,或者旅行商问题,最优和次优对于成本控制和资源安排来说没有很大区别

但是对于另一些问题,比如前面说的排序,比如非常严格的实时系统,次优就是错误,而不是一个勉强可以接受的结果

最为关键的是,如何权衡和妥协.

1.2-1

应用层的算法使用的应该非常多,最简单的比如访问计数,在简单的情况下可以逐渐加1,但是在高流量大并发下,这样的计数有问题,需要良好的算法才能维持计数的稳定性和准确性.

算法其实无处不在,虽然不一定会使用到多么复杂的,但是熟悉算法总会提供一个解决问题的好的方向和方法

1.2-2

设 8n^2 = 64nlnn,当n小于45时,插入排序比较快,当n大于45时,归并排序比较快

这里可以看得出,谈论算法的绝对执行效率,只需要考量算法输入规模的,我们平常讨论的大O,只是算法效率增长的规模,但其对应于具体的算法实现要求,还是要结合实际来判断的.

1.2-3

设 100n^2 = 2^n , 求解方程即可