第一章 算法在计算机中的应用

第一章：

讲了算法(algorithm)的基本概念，以及算法的作用。(这些可以看书)

用个人的话来讲，你可以把算法当做一个解决问题的方法，就像数学里的各种公式一样，你也可以把他们认为是一种算法。算法无处不在，而且算法必须存在，否则我们的生活都将变得缓慢，迟钝。

举个例子：我们平时出去游玩时，要事先查好路线，这时就可以用百度地图搜索从A地到B地的路线，地图上会给出最快的乘车路线，这些路线是怎么给出来的，就是用了最短路的算法，关于最短路的算法有很多，比如Dijkstra, Bellman, Floyd, SPFA等等，当然还有好多我不知道，但是通过这可以看出，算法可以让我们的生活变得更有效率。

当然，第一章也可以认为是给大家鼓气的一章，让大家发现算法的魅力，算法的强悍。大家都来爱上算法吧！

习题解答：
1.1-1 给出现实生活中需要排序的一个例子和计算凸壳的例子。
答：排序就有很多了，比如全校学生的成绩登录系统需要排序算法了。
凸壳则比较复杂了，比如在大海中打捞飞机的话需要根据一些重要的点计算搜 寻范围，需要确定最小搜索面积的话，需要求出凸壳的顶点集然后才能求出面积。

1.1-2 除速度外，在真实环境中还可能使用哪些其他有关效率的量度。
答：比如功率之类的物理变量。

1.1-3 选择一种你以前已知的数据结构，并讨论其优势和局限。
答：链表，优势在于它是比较底层的数据结构，可以比较方便的实现比较高级的数据结构。局限在于效率比较低，而且空间占用普通。

1.1-4 前面给出的最短路径与旅行商问题有哪些相似之处？有哪些不同？
答：相似之处都是要求出一个最短路径，但最短路径是定点求路线，而旅行商是点和路线一起求，在复杂度上比最短路径要高。

1.1-5 提供一个现实生活的问题，其中只有最佳解才行。
答：我在这提出一个我没有解决的问题，是携程上比赛的一个题目，希望有大神能指导下怎么做。题目大意是这样的：给出N个点，这N个点不能全部在一条直线上，确定一个周长最小的矩形将这N个点全部包括进去。

1.2-1 给出在应用层需要算法内容的应用的一个例子，并讨论涉及算法的功能。
答：比如大家比较喜欢LOL的人物移动的时候是怎么走的？是不是按最短的曲线走的？这时就需要算法里的最短路径算法了对吧，否则点一个地点，等人走到那的时候可能已经大半个世纪过去了。最短路径实现的就是确定按照人的直接意愿引导英雄走向目标地点的最短路径。

1.2-2 假设我们正比较插入与归并排序在相同机器上的实现。对规模为n的输入，插入排序运行8n^2步，而归并排序运行64nlgn步。问对哪些n值，插入排序优于归并？
答： 令 8n^2 < 64nlgn =>
化简得n < 8lgn =>
2^(n/8) < 2^(lgn) =>
2^(n/8) < n =>
令t=n/8 , n=8t =>
2^t < 8t =>
制表：
        1    2    3    4    5    6
8t    8  16    24 32  40  48
2^t  2  4       8   16  32  64
当t=0 8t=0 2^t=1
当t=0.2, 8t=1.6 2^t=1.15
当t=5.1， 8t=40.8 2^t=34.3
当t=5.4, 8t=43.2 2^t=42.2
当t=5.5, 8t=44 2^t=45.25
所以，当0.2 < t < 5.5时，即1 < n < 44时，插入排序优于归并。

1.2-3 n的最小值为何值时，运行时间为100n^2的一个算法快于运行时间为2^n的算法？
答：令100n^2<2^n =>

由图可得当n>14.325时，满足不等式，又n为正整数，所以n取最小值15。

思考题
1-1运行时间的比较
答：具体的答案数据就不列出来了，但可以肯定的是，从上到下，算法效率是逐渐降低的，意思是说一个算法若能做到lgn的效率是极佳的，而如果做到n！的话则是最不可取的了。