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

2017-08-26  本文已影响0人  Nautilus1

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
上一篇 下一篇

猜你喜欢

热点阅读