第一章 算法在计算中的作用

练习

1.1-1 给出现实生活中需要排序的一个例子或者现实生活中需要计算凸壳的一个例子。

排序：购物网站需要知道当前商品下价格最低的店铺或者销量最高的店铺。

凸壳：当需要在一片海域搜救时，必须通过重要的点来计算搜寻范围。只有确定了凸壳的面积，才能确定最小搜救面积。

1.1-2 除速度外，在真实环境中还可能使用哪些其他有关于效率的量度？

功率，也就是焦耳/秒。代表一个物体制造或者消耗能量的速度。

1.1-3 选择一种你以前已知的数据结构，并讨论起优势和局限。

数组，C语言内置的数据结构。

优势：可以进行随机访问所以访问的速度很快。

劣势：但是无法快速的插入或者删除，并且也不能随意的改变容量。

1.1-4 前面给出的最短路径与旅行商问题有哪些相似之处？又有哪些不同？

相似：最短路和旅行商问题都是计算最短路径的问题。

不同：普通的最短路径是定点求解，而旅行商问题是求解点和最短路径，复杂度更高。

1.1-5 提供一个现实生活的问题，其中只有最优解才行。然后提供一个问题，其中近似最优解也足够好。

唯一解：银行卡在取款的时候，账号必须精确匹配密码才能进行取款操作。

近似解：电灯的电压只要控制在一定的范围之内就可以很好的工作。

练习

1.2-1 给出在应用层需要算法应用的一个例子，并讨论涉及算法的功能。

计算一个电子地图上出发地和目的地之间最短的路程。该应用需要使用以距离为权重的无向图最短路算法。

1.2-2 假设我们正比较插入排序与归并排序在相同的机器上实现。对规模为n的输入，插入排序运行8n^2步，而归并排序运行64nlgn步，问对哪些n值，插入排序优于归并排序？

首先联立，令：8n^2 = 64nlgn; 然后计算出n为43.5593时等式成立，即输入规模n不超过43时插入排序优于归并排序。

1.2-3 n的最小值为何值时，运行时间为 100n^2 的一个算法在相同的机器上快于运行时间为 2^n 的另一个算法？

首先联立，令：100n^2 = 2^n；计算出n = 14.32，也就是说当输入规模大于15时，前者快于后者。