算法

算法是一项技术.

非形式的说,

算法

就是任何良定义的计算过程,该过程取某个值或值的集合作为

输入

并产生某个值或值的集合作为

输出

.这样算法就是把输入转换成输出的计算步骤的一个序列.

也可以把算法看成是用于求解良说明的

计算问题

的工具.问题陈述说明了期望的输入/输出关系.算法则描述一个特定的计算过程来实现该输入/输出关系.

算法的的某个输入序列称为排序问题的一个

实例

,一般来说,

问题实例

由计算该问题解所必需的(满足问题陈述中强加的各种约束)输入组成.

排序算法

中,判断哪个算法最好依赖于以下因素:将被排序的项数,这些项已被稍微排序的程度,关于项值的可能限制,计算机的体系结构,以及将使用的存储设备的种类.

若对每个输入实例,算法都以正确的输出停机,则称该算法是

正确的

,并称正确的算法

解决了

给定的计算问题.

不正确的算法对某些输入实例可能根本不停机,也可能以不正确的回答停机.与人们的期望的相反,不正确的算法只有其错误率可控有时可能是有用的.但是通常我们只关心正确的算法.

许多有趣的算法问题共有的两个特征:

1. 存在许多候选解,但绝大多数候选解都没有解决手头的问题.寻找一个
   
   真正的解
   
   或一个
   
   最好的解
   
   可能是一个很大的挑战.
2. 存在实际应用.

数据结构

是一种存储和组织数据的方式,旨在便于访问和修改.没有一种单一的数据结构对所有用途有效,所以重要的是知道几种

数据结构的优势和局限

.

也许在某一天你会遇到一个问题,一时无法很快找到一个已有的算法来解决它.因此我们需要学习一些

算法设计与分析的技术

,以便我们能够自行设计算法,证明其正确性和理解其效率.

有一些问题,目前还不知道有效的解法,例如

NP完全的

.

为什么NP完全问题有趣呢?

• 对于NP完全问题,是否存在有效算法是未知的.
• NP完全问题集具有一个非凡的性质:如果任何一个NP完全问题存在有效算法,那么所有的NP完全问题都存在有效算法.
• 有几个NP完全问题类似于一些有着已知有效算法的问题.

“旅行商问题”

就是比较著名的NP完全问题,它没有已知的有效算法.然而,在某些假设条件下,我们知道一些有效算法,它们给出一个离最小问题可能解不太远的总距离.需要了解一些这样的”近似算法”.

为什么说算法是一种技术呢?


假设计算机是无限快的并且计算机存储器是免费的.你还有什么理由来研究算法吗?即使只是因为你还想证明你的解法会终止并以正确的答案终止,那么回答也是肯定的.

计算机也许是快的,但它们不是无限快,存储器也许是廉价的,但不是免费的.所以计算时间是一种有限资源,存储器中的空间也一样.

为求解相同问题而设计的不同算法在效率方面常常具有显著的差别,这些差别可能比由于硬件和软件造成的差别要重要的多.

插入排序

为了排序n个项,该算法所花时间大致等于c1n^2,其中c1是一个不依赖于n的常数.也就是说该算法所花费的时间大致与n^2成正比.而

归并排序

为了排序n个项,该算法所花时间大致等于c2nlgn,其中lgn代表log2n且c2是另一个不依赖于n的常数.与归并序相比,插入排序通常具有一个较小的常数因子,所以c1<c2.虽然对于小的输入规模,插入排序通常比归并排序要快,但是一旦输入规模n变得足够大,归并排序lgn对n的优点将足以补偿常数因子的差别.不管c1比c2小多少,总会存在一个交叉点,超出这个点,归并排序更快.

练习:

1. 假设我们正比较插入排序与归并排序在相同机器上的实现.对规模为n的输入,插入排序运行8n^2不,而归并排序运行64nlgn步.问对哪些n值,插入排序优于归并排序?
2. n的最小值为何值时,运行时间为100n^2的一个算法在相同机器上快于运行时间为2^n的另一个算法?

思考:

(

运行时间的比较

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

提示:lgn=1000,√n=100,n=100,nlgn=100,n^2=100,n^3=100,2^n=100,n!=100.