【算法导论】第1章 算法在计算中的作用

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

  排序：招生考试中将考生的成绩从高到低排序，择优录取。
  计算凸壳：墙面安装了520个小灯泡，以其中一些灯泡为顶点组成的凸多边形为电线线路，线路包含所有520个灯泡，找出使线路构成的凸多边形达到最小的所有灯泡。

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

  占用资源大小、结果精度等等。

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

  单链表
  优势：不需要连续的存储空间,插入删除元素不需要大量移动
  局限：不能随机访问

• 1.1-4 最短路径与旅行商问题有哪些相似与不同之处？

  相似：都是寻找最短的路线问题
  不同：最短路径问题是在已知的路线中找到两点间的最短距离；旅行商问题是返回一个点的更多路径的最短路径

• 1.1-5 提供一个现实生活中的问题，其中必须有最佳解才行。另外在提供一个问题，其中近似最佳的一个解也足够。

  计算凸壳（计算最小凸多边形）
  旅行商问题（送货火车每天的额最小行驶距离）

@[TOC](1.2 作为一种技术的算法)

• 1.2-1 给出在应用层需要算法内容的应用的一个例子。

  导航系统。给用户提供更准确更短的的行进路线。

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

  8n^2 < 64nlgn 及 2^n < n^8 ，向下取整得n <= 43

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

  同1.2-2得, n >= 15

@TOC

• 1-1 假设求解问题的算法需要f(n)毫秒，对下表的每个函数f(n)和时间t，确定可以在时间t内求解的问题的最大规模n。