算法设计与分析(3)

则称T(n)=O(f(n))（或称算法在O(f(n))中）。

大O符号用来描述增长率的上限，表示T(n)的增长最多像f(n)增长的那样快，也就是说，当输入规模为n时，算法消耗时间的最大值，这个上限的阶越低，结果就越有价值。

大O符号的含义如图1.4所示，为了说明这个定义，将问题规模n扩展为实数。

执

c×f(n) 行

次 T(n) 数

n0之前的 情况无关紧要

n0 问题规模n

图1.4 大O符号的含义

应该注意的是，定义1.1给了很大的自由度来选择常量c和n0的特定值，例如，下列推导都是合理的：

100n＋5≤100n＋n(当n≥5)=101n＝O(n) (c＝101，n0＝5) 100n＋5≤100n＋5n(当n≥1)=105n＝O(n) (c＝105，n0＝1) 2. 大Ω符号

定义1.2 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)=Ω(g(n))（或称算法在Ω(g(n))中）。

大Ω符号用来描述增长率的下限，也就是说，当输入规模为n时，算法消耗时间的最小值。与大Ｏ符号对称，这个下限的阶越高，结果就越有价值。

大Ω符号的含义如图1.5所示。

T(n) 执

行

c×g(n) 次

数 n0之前的情况无关

紧要 n0 问题规模n

图1.5 大Ω符号的含义

大Ω符号常用来分析某个问题或某类算法的时间下界。例如，矩阵乘法问题的时间下界为Ω(n2)，是指任何两个n×n矩阵相乘的算法的时间复杂性不会小于n2，基于

11

比较的排序算法的时间下界为Ω(nlog2n)，是指无法设计出基于比较的排序算法，其时间复杂性小于nlog2n。

大Ω符号常常与大O符号配合以证明某问题的一个特定算法是该问题的最优算法，或是该问题中的某算法类中的最优算法。 3. Θ符号

定义1.3 若存在三个正的常数c1、c2和n0，对于任意n≥n0，都有c1×f(n)≥T(n)≥c2×f(n)，则称T(n)=Θ(f(n))。

Θ符号意味着T(n)与f(n)同阶，用来表示算法的精确阶。Θ符号的含义如图1.6所示。

c1×f(n) 执

行 T(n) 次

c2×f(n) 数 n0之前的情况无关 紧要

n0 问题规模n 图1.6 Θ符号的含义

下面举例说明大O、大Ω和Θ三种渐进符号的使用。 例1.1 T(n)＝3n-1

【解答】当n≥1时，3n-1≤3n＝O(n)

当n≥1时，3n-1≥3n-n＝2n＝Ω(n)

当n≥1时，3n≥3n-1≥2n，则3n-1＝Θ(n)

例1.2 T(n)＝5n2＋8n＋1 【解答】当n≥1时，5n2＋8n＋1≤5n2＋8n＋n＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)

当n≥1时，5n2＋8n＋1≥5n2＝Ω(n2)

当n≥1时，14n2≥5n2＋8n＋1≥5n2，则5n2＋8n＋1＝Θ(n2) 定理1.1 若T(n)=amnm +am-1nm-1 + ? +a1n+a0（am>0），则有T(n)=O(nm)，且T(n)=Ω(n m)，因此，有T(n)=Θ(n m)。

1.2.2 最好、最坏和平均情况

影响算法时间代价的最主要因素是问题规模，但是，对于某些算法，即使问题规模相同，如果输入数据不同，其时间代价也不同。

12

例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?12

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法设计与分析(3)在线全文阅读。