计算机算法分析与设计

计算机算法分析与设计

学习目标

■掌握算法分析与设计的基本理论

■掌握进行算法分析与设计的基本方法

（时间、空间复杂度分析，算法正确性

的证明）

■掌握计算机领域中常用的非数值计算方

法，并学会用这些算法解决实际问题

课程要求

■教学方式：理论（32学时），实践（工6

学时）

■考核方式：考试（80%））+实验作业

（20%）

■课程学分：3

■先修课程：《离散数学》《数据结构》

《数值分析》《C语言程序设计》

授课教材

■选用教材：

《计算机算法基础》（第二版）

余祥宣，崔国华，邹海明华中科技大学

出版社

■参考书目：

《算法引论》张益新，沈雁国防科技大

学出版社

《算法设计与分析》周培德机械工业出

版社

第一章导引

一■计算机算法分析与设计是面向设计的、处于核心地

位的教育课程

一■计算机算法是计算机科学和计算机应用的核心。

1.什么是算法？

2•如何分析算法?

3.如何表示算法?

4.基本数据结构

工.什么是算法

厂数值计算方法（求解数值问题，插

值计算、数值积分等）

算法Y

非数值计算方法（求解非数值问题,

I主要进行判断比较）

算法笼统的定义：求解一确定类问题的任意一种

特殊方法。

非形式描述：算法就是一组有穷的规则，它规定

了解决某一特定类型问题的一系列运算。

例工求两个正整数m,n的最大公因子

算法工・工欧几里得算法

输入：正整数m和n

输出：m和n的最大公因子

第一步：求余数。

第二步：判断r=0?,若是，终止（n为

答案），否则，转第三步。

第三步：互换返回第一

例工求两个正整数最大公因子的一个实例

假设m=21和n=45,求21和45的最大公因子

第一步：r=m%n=21<%)45=21；

第二步：r不等于0,转入第三步；

第三步：互换，m=n=45zn=r=21,返回第一步。

第一步：r=m%n=45%21=3；

第二步：r不等于0,转入第三步；

第三步：互换，m=n=21zn=r=3,返回第一步。

第一步：r=m%n=21%3=0；

第二步：「等于0,算法结束，3即为21和45的最大

公因子。

算法的五个重要特性

■确定性

每一种运算必须要有确切的定义，无二义性

■可行性

运算都是基本运算，原理上能在有限时间内完成

■输入

有工个或多个输入

■输出

一个或多个输出

■有穷性

在执行了有穷步运算后终止

算法的特性

■凡是算法，都必须满足以上五条特性。

■只满足前四条特性的一组规则不能称之为

算法，只能叫做计算过程。

■操作系统就是计算过程的一个典型例子。

设计操作系统的目的是为了控制作业的运

行，当没有作业时，这一计算过程并不终

止，而是处于等待状态，一直等到一个新

的作业的进入。

算法学习的五个内容

■如何设计算法

运用一些基本设计策略规划算法

■如何表示算法

用恰当的方式表示算法

■如何确认算法

算法正确性的证明（算法确认algorithmvalidation）

■如何分析算法

通过时间和空间复杂度的分析，确定算法的优劣

■如何测试程序

测试程序是否会产生错误的结果

2.如何分析算法

■算法分析是对一个算法需要多少计算时间和存储

空间作定量的分析。

■算法分析步骤：

■首先确定使用那些运算以及执行这些运算所用

的时间。（运算包括基本数值运算和一些更基

本的任意长序列的运算）

■其次是要确定出能反映算法在各种情况下工作

的数据集。（即要求我们编造出能产生最好、

最坏和有代表性情况的数据配置，通过使用这

些数据来运行算法，以更了解算法的性能）

全面分析一个算法的两个阶段

■事前分析(apriorianalysis)

■求出该算法的一个时间限界函数(一些关于参

数的函数)

■事前分析只限于每条语句的频率计数一

(frequencycount,该语句的执行次数，

与所用的机器无关，且独立于程序设计语言，

可由算法直接确定)

■事后测试(aposterioritesting)

■收集此算法的实际执行时间和占用空间的统计

资料

例3：频率计数例子

■考虑语句x(x+y在下面三个程序段中的频率计数

begin|begin

begin

for*1tondo|fortondo

x(x+y

x^x+y|forj(ltondo

endrepeatx^x+y

Endrepeat

IRepeat

|End

FC:1FC:n

IFC:n2

计算时间的渐进估计表示

■定义工,工如果存在两个正常数c和n。，对于所有

的nNn。，有

|f(n)|<c|g(n)|

则记作：f(n)=O(g(n))

■因此，当说一个算法具有O(g(n))的计算时间

时，指的就是如果此算法用n值不变的同一类数

据在某台机器上运行时，所用的时间总是小于

|g(n)|的一个常数倍。

■g(n)是计算时间f(n)的一个上界函数，f(n)的

数量级就是g(n)

时间的渐进估计表示

m

■定理工■工^A(n)=amn+...+a1n+a0^

一个m次多项式,则A(n)=O(nm)。

证明：取11。=工，当n之n。时利用A(n)的定义

和一个简单的不等式，有

m

|A(n)|<|am|n+...+|a1|n+|a0I

mm

W(|am|+|am.1|/n...+|a0|/n)n

m

W(|am|+|am,1|...+|a0|)n

取c二|am|+|am.1|...+|a0|,定理得证。

时间的渐进估计表示

■定理表明，变量n的固定阶数为m的任一多

项式，与此多项式的最高阶nm同阶。因此,

一个计算时间为m阶多项式的算法，其时

间都可以用O(nm)来表示。

■例如，一个算法的数量级为

Cilim'c2nm2,...Cknmk的k个语句，贝［J算

法的数量级及计算时间就是

mlm2mkm

c1n+c2n+...+ckn=O(n)

其中m=IEi<k}

算法的分类

■从计算时间上可把算法分为两类

■多项式时间算法(polynomialtime

algorithm):可用多项式来对其计算时间

限界的算法。以下六种计算时间的多项式时

间算法是最为常见的

O(l)<O(logn)<O(n)<O(nlogn)<O(n2)<

O(n3)

■指数时间算法(exponentialtime

algorithm):计算时间用指数函数限界的算法

O(2n)<O(n!)<O(nn)

对于问题输入长度n取不同值，各种不同的时间复

费性函数的算法，在机器上的运行所需时间如下所

TN：

nlognnlognn2n32n

100112

212484

428166416

832464512256

16464256409665536

32516010243276842949

67296

时间的渐进估计表示

■定义1.2如果存在两个正常数(:和n。，对于所有的

n>n0,有

|f(n)|>c|g(n)|

则记作:f(n)=n(g(n))

■定义1.3如果存在两个正常数白人2和n。，对于所

有的n二n。，有

J|g(n)|<|f(n)|<c2|g(n)|

则记作：f(n)=e(g(n))

常用的整数求和公式

SI=®(n)

IWiwJI

=n(n+l)/2=0(rf)

iwWti

2r=n(n+l)(2n+l)/6=。(n)

IWi，

2K二®(nkH)

IWiWu

3.如何表示算法

■将算法的基本思想和基本步骤用语言表示出来，

便于阅读并能很容易地用人工或机器翻译成其他

实际使用的程序设计语言。

■用SPARKS语言写算法

■SPARKS语言的组成

■基本数据类型

整型（integer）,实型（float）,布尔型（boolean）,字符

型（char）

■保留字

具有特殊含义的标识符，用黑体字表示

SPARKS语言的组成(1)

■变量命名规则

■以字母开头，不允许使用特殊字符，不要太长，不

允许与任何保留字重复。

■语句：以分号作为语句结束的标志

■赋值语句：V变量〉QV表达式〉

■布尔值：TrueFalse

■逻辑运算符：

and,orrnot

■关系运算符：

■数组：任意整数下界和上界的多维数组

SPARKS语言的组成(2)

■条件语句

if条件thensi或if条件then

elses2si

endifendif

■Case语句

case

：条件l：sx

：条件n:sn

:else:sn+1

endcase

SPARKS语言的组成(3)

■循环语句

while条件doloop

SS

Repeatuntil条件repeat

Forvble^starttofinishbyincrementdo

S

Repeat

SPARKS语言的组成(4)

・过程(函数)

ProcedureName(v参数歹U表》)

v说明部分〉

S

Return(v表达式〉)

EndName

■局部变量(localvariabl)

在当前的过程中说明的变量

■全局变量(globalvariabl)

在已包含当前过程的过程中说明为局部变量的变量

■形式参数(formalparameter)

参数表中的一个标识符

1.4基本数据结构（略）

■栈和队列

■栈的运算

■队列的运算

■树

■二元树

■堆

■二分检索树

■图

1.5递归和消去递归

■递归

直接调用自己或间接通过一些语句调用自己

优点：描述某些数学问题非常自然，证明算法

很容易。

缺点：执行时间、空间消耗多

一个递归问题可分为“回推”和“递推”两个

阶段回推

未知已知

递推

递归例子：Fibonacci数列

1/n=0-

■定义非递归部分，终止条件

工,n=l-

F(n)=

递归部分，起始条件

F(n-l)+F(n-2)fn>l

■求Fibonacci数列算法

ProcedureF(n)

integern

ifn<lthenreturn(l)

elsereturn(F(n-l)+F(n-2))

endif

EndF

用递归实现求最大公因数

ProcedureGCD(aAb)

ifb=0thenreturn(a)

elsereturn(GCD(bzamodb))