算法概述

算法与程序

对于计算机科学来说，算法（Algorithm）的概念至关重要。例如，在一个大型软件系统的开发中，设计出有效的算法将起决定性的作用。通俗地讲，算法是指解决问题的一种方法或一个过程。更严格地讲，算法是由若干条指令组成的有穷序列，且满足下述4条性质。

①输入：有零个或多个由外部提供的量作为算法的输入。

输出：算法产生至少一个量作为输出。

③确定性：组成算法的每条指令是清晰的，无歧义的。

④有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。程序（Program）与算法不同。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质④。例如，操作系统是一个在无限循环中执行的程序，因而不是一个算法。然而，操作系统的各种任务可以看成一些单独的问题，每个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

描述算法可以有多种方式，如自然语言方式、表格方式等。本书采用C++语言描述算法。C++语言的优点是类型丰富、语句精炼，具有面向过程和面向对象的双重特点。用C++语言来描述算法，可使整个算法结构紧凑，可读性强。在本书中，有时为了更好地阐明算法的思路，还采用C++语言与自然语言相结合的方式来描述算法。

算法复杂性分析

算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。对计算机资源，最重要的是时间和空间（即存储器）资源。因此，算法的复杂性有时间复杂性和空间复杂性之分。对于任意给定的问题，设计出复杂性尽可能低的算法是设计算法时追求的一个重要目标。另一方面，当给定的问题已有多种算法时，选择复杂性最低者是选用算法时遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。更确切地说，算法的复杂性是算法运行需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性。这个量应该集中反映算法的效率，并从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于要解的问题的规模，算法的输入和算法本身的函数。如果分别用N、1和A表示算法要解的问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么应该有C=F(N,I,A)，其中F(N，I，A)是一个由N、I和A确定的三元函数。如果把时间复杂性和空间复杂性分开，并分别用T和S来表示,应该有T=T(N,I,A)和S=T(N,I,A)。通常，A隐含在复杂性函数名当中，因而将T和S分别简写为T=T(N，I)和S=S(N，I)。

由于时间复杂性与空间复杂性概念类同，计量方法相似，且空间复杂性分析相对简单些，因此本书将主要讨论时间复杂性。现在的问题是如何将复杂性函数具体化，即对于给定的N.1和A，如何导出 T(N，1)和S(N，1)的数学表达式，从而给出计算T(N,1)和S(N,I)的法则。下面以T(N,1）为例，将复杂性函数具体化。

T(N，1)应该是算法在一台抽象的计算机上运行所需要的时间。设此抽象的计算机提供的元运算有k种，分别记为O1,O2，…，Ok，每执行一次这些元运算所需要时间分别为t。对于给定的算法 A，经统计，用到元运算 0;的次数为e（i=1,2，…,k)。对于每个i(1≤i≤k),e是N和1的函数，即e=e(N，I)。因此有

T(N,I)=Σ(i=1,i<=k)ti*ei(N,I)

i=1式中，1（i=1,2,…，k）是与N和I无关的常数。

显然，不可能对规模为N的每种合法的输入I都统计e(N,I)(i=1,2,…，k)，因此T(N,I)的表达式需要进一步简化，或者说，只能在规模为N的某些或某类有代表性的合法输入中统计相应的ei（i=1,2，…，k）来评价其时间复杂性。

本书只考虑三种情况下的时间复杂性，即最坏情况、最好情况和平均情况下的时间复杂

性，分别记为Tmax（N)、Tmin(N)和Tavg(N)。