算法设计与分析

例1.3 在一维整型数组A[n]中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k），顺序查找算法如下：

算法1.2——顺序查找 int Find(int A[ ], int n) { for (i=0; i

一般来说，最好情况不能作为算法性能的代表，因为它发生的概率太小，对于条件的考虑太乐观了。但是，当最好情况出现的概率较大的时候，应该分析最好情况。

分析最差情况有一个好处：它能让你知道算法的运行时间最坏能坏到什么程度，这一点在实时系统中尤其重要。

通常需要分析平均情况的时间代价，特别是算法要处理不同的输入时，但它要求已知输入数据是如何分布的。通常假设是等概率分布，例如，上面提到的顺序查找算法平均情况下的时间性能，如果数据不是等概率分布，那么算法的平均情况就不一定是比较一半的元素了。

1.2.3 非递归算法的分析

从算法是否递归调用的角度来说，可以将算法分为非递归算法和递归算法。

对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。

例1.4 在一个整型数组中查找最小值元素，具体算法如下： 算法1.3——求数组最小值 int ArrayMin(int a[ ], int n) {

min=a[0];

for (i=1; i

13

在算法1.3中，问题规模显然是数组中的元素个数，执行最频繁的操作是在for循环中，循环体中包含两条语句：比较和赋值，应该把哪一个作为基本语句呢？由于每做一次循环都会进行一次比较，而赋值语句却不一定执行，所以，应该把比较运算作为该算法的基本语句。接下来考虑基本语句的执行次数，由于每执行一次循环就会做一次比较，而循环变量i从1到n-1之间的每个值都会做一次循环，可得到如下求和表达式：

T(n)??1

i?1n?1用渐进符号表示这个求和表达式：

T(n)??1?n?1?O(n)

i?1n?1 非递归算法分析的一般步骤是：

1．决定用哪个（或哪些）参数作为算法问题规模的度量

在大多数情况下，问题规模是很容易确定的，可以从问题的描述中得到。

2．找出算法中的基本语句

算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体。

3．检查基本语句的执行次数是否只依赖于问题规模

如果基本语句的执行次数还依赖于其他一些特性（如数据的初始分布），则最好情况、最坏情况和平均情况的效率需要分别研究。

4．建立基本语句执行次数的求和表达式

计算基本语句执行的次数，建立一个代表算法运行时间的求和表达式。

5．用渐进符号表示这个求和表达式

计算基本语句执行次数的数量级，用大O符号来描述算法增长率的上限。

1.2.4 递归算法的分析

递归算法实际上是一种分而治之的方法，它把复杂问题分解为若干个简单问题来求解。对递归算法时间复杂性的分析，关键是根据递归过程建立递推关系式，然后求解这个递推关系式。下面介绍几种求解递推关系式的技术。 1. 猜测技术

猜测技术首先对递推关系式估计一个上限，然后试着证明它正确。如果给出了一个正确的上限估计，经过归纳证明就可以验证事实。如果证明成功，那么就试着收缩上限。如果证明失败，那么就放松限制再试着证明，一旦上限符合要求就可以结束了。当只求解算法的近似复杂性时这是一种很有用的技术。

14

例1.5 使用猜测技术分析二路归并排序算法的时间复杂性。

二路归并排序是将一个长度为n的记录序列分成两部分，分别对每一部分完成归并排序，最后把两个子序列合并到一起。其运行时间用下面的递推式描述：

1?T(n)???2T(n2)?nn?2 n?2 也就是说，在序列长度为n的情况下，算法的代价是序列长度为n/2时代价的两倍（对归并排序的递归调用）加上n（把两个子序列合并在一起）。

假定T(n)≤n2，并证明这个猜测是正确的。在证明中，为了计算方便，假定n=2k。 对于最基本的情况，T(2)=1≤22；对于所有i≤n，假设T(i)≤i2，而

T(2n)=2T(n)+2n≤2n2+2n≤4n2＝(2n)2

由此，T(n)=O(n2)成立。

O(n2)是一个最小上限吗？如果猜测更小一些，例如对于某个常数c，T(n)≤cn，很明显，这样做不行。所以，真正的代价一定在n和n2之间。

现在试一试T(n)≤nlog2n。

对于最基本的情况，T(2)=1≤(2log22)=2；对于所有i≤n，假设T(i)≤ilog2i，而

T(2n)≤2T(n)+2n≤2nlog2n+2n＝2n(log2n+1)≤2nlog2(2n) 这就是我们要证明的，T(n)=O(nlog2n)。 2. 扩展递归技术

扩展递归技术是将递推关系式中等式右边的项根据递推式进行替换，这称为扩展。扩展后的项被再次扩展，依此下去，会得到一个求和表达式，然后就可以借助于求和技术了。

例1.6 使用扩展递归技术分析下面递推式的时间复杂性。

7?T(n)??2?2T(n2)?5nn?1n?1

简单起见，假定n=2k。将递推式像下面这样扩展：

T(n)?2T(n2)?5n2?2(2T(n4)?5(n2)2)?5n2

?2(2(2T(n8)?5(n4)2)?5(n2)2)?5n2?2kT(1)?2k?15(n222)???2?5()?5n2k?12n

最后这个表达式可以使用如下的求和表示：

12?n?T(n)?7n?5??i??7n?5n2(2?k?1)?7n?5n2(2?)?10n2?3n?10n2?O(n2)2ni?0?2?

15

k?123. 通用分治递推式

递归算法分析的第三种技术是利用通用分治递推式：

c?T(n)??k?aT(nb)?cnn?1n?1

其中a，b，c，k都是常数。这个递推式描述了大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问题的解需要的工作量。下面使用扩展递归技术对通用分治递推式进行推导，并假定n=bm。

?n?T(n)?aT???cnk?b??n??n??a(aT?2??c??)?cnk?b??b??aT(1)?ammm?1k?n??n?c?m?1????ac???cnk?b??b?kkk?n??c?am?i?m?i??b?i?0?c?am?ibiki?0m

?bkm?ca???i?0?am????ibk这个求和是一个几何级数，其值依赖于比率r?a，注意到am=alogbn=nlogba，有

以下三种情况：

1，由于am= nlogba ，所以T(n)=O(nlogba)。 1?ri?0m （2）r=1：?ri?m?1?logbn?1，由于am= nlogba =nk ，所以T(n)=O(nklogbn)。

（1）r<1：?ri?i?0mrm?1?1mmkmk （3）r>1：?r??O(rm)，所以，T(n)=O(ar)=O(b)=O(n)。

r?1i?0mi对通用分治递推式的推导概括为下面的主定理：

?O(nlogba)?T(n)??O(nklogbn)?kO(n)?a?bka?bk a?bk 16