1.1 算法

算法就是把输入转换成输出的计算步骤的一个序列。问题陈述说明期望的输入/输出关系，算法则描述一个特定的计算过程来实现该输入/输出关系。问题的一个输入序列称为一个实例，若对于该问题的每个实例，算法都以正确的输出停机，则称该算法正确地解决了给定计算问题。说明算法的唯一要求是必须精确描述所要遵循的计算过程。

数据结构

数据结构是存储组织数据的方法，旨在便于访问和修改。了解基本数据结构的优势和局限。

难题

NP完全问题：

1. 是否存在有效算法是未知的
2. 任何一个NP完全问题存在有效算法，则所有NP完全问题都存在
3. 几个NP完全问题类似于一些已知有效算法的问题

并行性

为了从多核计算机获得最佳性能，设计算法时考虑并行性。

练习

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

答：搜索引擎的页面排序、车票按价格、地点排序等。
凸包定义：

1. 对于一个集合D，D中任意有限个点的线性组合的全体称为D的凸包。
2. 对于一个集合D，所有包含D的凸集之交称为D的凸包。
   两定义等价。D的凸包可以用D内所有点(D1，...Dn)的线性组合来构造。在二维欧几里得空间中，凸包可想象为一条刚好包着所有点的橡皮圈。点集Q的凸包是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。一组平面上的点，求一个包含所有点的最小的凸多边形就是凸包问题。凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。

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

答：空间复杂度、是否易于实现、安全、维护性。

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

答：数组随机存取容易，但插入删除困难。链表插入删除容易，但不能随机存取。

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

答：同样在一个图中找最短路径。但是约束不同：最短路仅要求两点之间距离最短的路线，旅行商问题需要经过几个固定的点后回到起点。

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

答：图像、语音识别要求准确率高才有实际用途。现实两城市之间的最短路近似最佳即可。

---

---

---

1.2 作为一种技术的算法

效率

求解相同问题的不同算法在效率上有显著差别。以排序为例，插入排序复杂度O（n^2），归并排序O（nlgn）。小规模输入插入排序通常更快，但超过一个交叉点后归并排序更快，且问题规模越大优势越大。

练习

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

答：地图导航，需要最短路算法。

1.2-2 假设我们正比较插入与归并排序在相同机器上的实现。对规模为n的输入，插入排序运行 时间t内求解问题的最大规模n