算法分析课件第01章-PPT幻灯片

基本内容导引（第一、二章）基本的算法设计策略分治法（第四章）贪心方法（第五章）动态规划（第六章）回溯法（第八章）分支－限界法（第九章）基本算法分析方法NP-难度和NP-完全问题（第十章）学习目标掌握基本的算法设计方法掌握分析算法的基本方法（时间、空间复杂度分析）灵活运用基本的算法设计方法，用于解决实际问题第二章导引2.1算法2.2分析算法及数学基础2.3用SPARKS语言写算法2.4基本数据结构二、算法的五个重要特性算法(Algorithm)确定性

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

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

有0个或多个输入输出

一个或多个输出有穷性

在执行了有穷步运算后终止Notes：仅仅有穷还不够，还要在现代计算机上有效才行程序(Program)(计算过程)程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(5)有穷性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。程序=算法+数据结构(ByWirth

)用计算机求解问题的步骤设计、确认、分析、编码、检查、调试、计时证明正确性分析算法理解问题精确解或近似解算法设计策略选择数据结构设计算法设计程序三、算法学习的五个内容如何设计算法运用一些基本设计策略规划算法如何表示算法用恰当的方式表示算法如何确认算法算法正确性的证明(算法确认algorithmvalidation)如何分析算法通过时间和空间复杂度的分析，确定算法的优劣如何测试程序测试程序是否会产生错误的结果设计高效算法SPARKS语言穷举、数学归纳法、反证法、构造性证明、测试目的是比较和改进算法调试和时空分布图第二章导引2.1算法2.2分析算法及数学基础2.3用SPARKS语言写算法2.4基本数据结构一、如何分析算法分析算法的目的

设计更高效的算法算法分析的前提

要求独立于具体的软硬件环境单纯分析算法 一台通用计算机(理想情况下)

顺序处理、每次一条指令、存储容量足够大、 存取时间恒定算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。2.2分析算法2.2分析算法一、如何分析算法算法分析的准备：首先确定使用哪些运算以及执行这些运算所用的时间。(运算包括基本运算和由一些更基本的任意长序列的运算所组成的复杂运算)其次是要确定出能反映算法在各种情况下工作的数据集。(即要求我们编造出能产生最好、最坏和有代表性情况的数据配置，通过使用这些数据来运行算法，以更了解算法的性能)

二、全面分析算法的两个阶段事前分析(aprioranalysis)求出该算法的一个时间限界函数(一些关于参数的函数)事前分析只限于每条语句的频率计数(frequencycount).语句的执行次数，与所用的机器无关，且独立于程序设计语言，可由算法直接确定事后测试(aposteriortesting)

收集此算法的实际执行时间和占用空间的统计资料2.2分析算法例：计算语句x

x+y在下面三个程序段中的频率计数beginx

x+yendFC:1beginfori

1tondo

x

x+yendFC:nbeginfori

1tondoforj

1tondo

x

x+yendFC:n2语句的数量级是指执行它的频率计数之和算法的数量级是指算法的所有语句的频率计数之和

确定一个算法的数量级十分重要，因为它在本质上反映了算法所需的计算时间。准确分析出一个算法的计算时间有时是很困难的，因此我们对算法的计算时间进行渐进表示。2.2分析算法算法复杂性分析形式化表述算法复杂性即算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。算法的时间复杂性（1）最坏情况下的时间复杂性Tmax(n)=max{T(I)|size(I)=n}（2）最好情况下的时间复杂性Tmin(n)=min{T(I)|size(I)=n}（3）平均情况下的时间复杂性Tavg(n)=其中I是问题规模为n的实例，p(I)是实例I出现的概率。2.2分析算法n：问题的规模f(n)：算法的计算时间g(n)：形式简单的函数(f(n)-g(n))/f(n)0，asn;在数学上，g(n)是f(n)的渐近表达式，是f(n)略去低阶项留下的主项。它比f(n)简单。三、计算时间的渐近表示定义1.1如果存在两个正常数c和n0，对于所有的n

n0，有|f(n)|

c|g(n)|，则记做f(n)

O(g(n)).

f(n)表示算法的计算时间，n是输入或输出量，g(n)是在事前分析中确定的某个形式的简单函数，f(n)与机器和语言有关，而g(n)是独立于机器和语言的。一个算法具有O(g(n))的计算时间是指如果这个算法用n

值不变的同一类数据在某台机器上运行时，所用的时间

总是小于|g(n)|的一个常数倍。

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

是g(n)。例子

f(n)

O(g(n))f(n)＝3n,

g(n)=4nf(n)＝n+1024,

g(n)=1025nf(n)＝2n2+11n-10,

g(n)=3n2f(n)＝n2,

g(n)=n3反例：f(n)＝n3,

g(n)=n2定理1.1若A(n)=amnm+……+a1n+a0是一个m次多项式，则A(n)=O(nm)定理1.1表明，变量n的最高阶数为m的任一多项式，与nm同阶。因此一个计算时间为m阶多项式的算法，其时间都可以用O(nm)来表示。

若一个算法有数量级为c1nm1，c2nm2，…cknmk的

k个语句，则算法的数量级及计算时间就是

c1nm1+c2nm2+…+cknmk=O(nm)

其中m=max{mi|1

i

k}从计算时间上对算法分类多项式时间算法(polynomialtimealgorithm):

用多项式来对其计算时间限界的算法

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间算法(exponentialtimealgorithm):

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

O(2n)<O(n!)<O(nn)数量级对算法有效性影响的实例不同时间复杂性函数的对比小规模数据中等规模数据定义1.2

如果存在两个正常数c和n0，对于所有的n

n0，有|f(n)|

c

|g(n)|，则记做f(n)

(g(n)).

这种情况称g(n)是计算时间f(n)的一个下界函数。在某些情况下，可能会出现g(n)既是f(n)的上界，又是它的下界，为此引入数学符号Θ来表示。定义1.3

如果存在两个正常数c1,c2和n0，对于所有的n

n0，有c1|g(n)|

|f(n)|

c2|g(n)|，则记作：f(n)=Θ(g(n)).渐近分析中函数比较a=f(n)；b=c

g(n)f(n)=O(g(n))

ab;f(n)=

(g(n))

ab;f(n)=

(g(n))

a=b;渐近表示函数的若干性质（1）传递性f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；f(n)=O(g(n))，g(n)=O

(h(n))

f(n)=O

(h(n))；f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；（2）反身性f(n)=

(f(n))；f(n)=O(f(n))；f(n)=

(f(n)).（3）对称性f(n)=

(g(n))

g(n)=

(f(n)).（4）互对称性f(n)=O(g(n))

g(n)=

(f(n))；（5）算术运算O(f(n))+O(g(n))=

O(max{f(n),g(n)})；O(f(n))+O(g(n))=

O(f(n)+g(n))；O(f(n))*O(g(n))=

O(f(n)*g(n))；O(cf(n))=

O(f(n))；f(n)=O(g(n))

O(f(n))+O(g(n))=

O(g(n))。也有类似性质，证明方法类似。规则O(f(n))+O(g(n))=

O(max{f(n),g(n)})的证明：对于任意f1(n)=O(f(n))，存在正常数c1和自然数n1，使得对所有n

n1，有f1(n)

c1f(n)。类似地，对于任意g1(n)=O(g(n))，存在正常数c2和自然数n2，使得对所有n

n2，有g1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。则对所有的n

n3，有f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n)=c3(f(n)+g(n))

2c3max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).规则O(f(n))+O(g(n))=

O(f(n)+g(n))的证明：对于任意f1(n)=O(f(n))，存在正常数c1和自然数n1，使得对所有n

n1，有f1(n)

c1f(n)。类似地，对于任意g1(n)=O(g(n))，存在正常数c2和自然数n2，使得对所有n

n2，有g1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=f(n)+g(n)。则对所有的n

n3，有O(f(n))+O(g(n))=f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n)=c3(f(n)+g(n))=c3h(n)=O(f(n)+g(n)).规则O(f(n))*O(g(n))=

O(f(n)*g(n))的证明：对于任意f1(n)=O(f(n))，存在正常数c1>1和自然数n1，使得对所有n

n1，有f1(n)

c1f(n)。类似地，对于任意g1(n)=O(g(n))，存在正常数c2>1和自然数n2，使得对所有n

n2，有g1(n)

c2g(n)。令c3=c1*c2，n3=max{n1,n2}，h(n)=f(n)*g(n)。则对所有的n

n3，有O(f(n))*O(g(n))=f1(n)*g1(n)

c1f(n)*c2g(n)=

c3f(n)*g(n)=c3h(n)=O(f(n)*g(n)).数学基础（1）求和公式通式算法渐近复杂性分析中常用函数（2）单调函数单调递增：m

n

f(m)

f(n);单调递减：m

n

f(m)

f(n);严格单调递增：m

<n

f(m)<f(n);严格单调递减：m

<n

f(m)>f(n).（3）取整函数

x：不大于x的最大整数；2.5

=22

=2

x：不小于x的最小整数。2.5=32=2取整函数的若干性质

x-1<x

x

x<x+1；

n/2

+n/2=n;

对于n

0，a,b>0，有：

n/a/b=n/ab;

n/a/b=n/ab;

a/b(a+(b-1))/b;

a/b(a-(b-1))/b;

f(x)=x,g(x)=x为单调递增函数。（4）多项式函数

p(n)=a0+a1n+a2n2+…+adnd；ad>0;

p(n)=

(nd);

p(n)=O(nk)

p(n)多项式有界；p(n)=O(1)

p(n)

c;（5）指数函数一些性质

对于正整数m,n和实数a>0:a0=1;

a1=a;

a-1=1/a;(am)n=amn;

(am)n=(an)m;

aman=

am+n;

a>1

an为单调递增函数;

a>1

nb=o(an)ex

1+x;|x|11+x

ex

1+x+x2;

ex

=1+x+(x2),asx0;（5）对数函数logn=log2n;

lgn=log10n;

lnn=logen;

logkn=(logn)k;loglogn=log(logn);fora

0,b

0,c

0|x|1forx>-1,foranya>0,

, logbn=o(na)（6）阶乘函数Stirling’sapproximation

时空分布图要求时钟及其精确度操作系统的工作方式处理噪声

增加输入规模增加执行次数时空分布图的做法用途比较同一问题的不同算法对算法改进前后进行比较主要内容2.1算法2.2分析算法及数学基础2.3用SPARKS语言写算法2.4基本数据结构2.3用SPARKS语言写算法

SPARKS语言的基本数据类型：整型(integer),实型(real),布尔型(boolean),字符型(char)

SPARKS语言的变量命名规则：以字母开头，不允许使用特殊字符，不允许与保留字重复

赋值语句：变量

表达式

逻辑运算符：and,or,not

关系运算符：

，

，

，

，

，

布尔值:true，false

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

integerA(l1:u1,…,ln:un);例:integerx,y;charch;例:integerA(1:10);realB(3:6,1:4);

SPARKS语言的条件语句if

条件

thens1endifif条件

thens1elses2endif

case

:

条件1:s1

…:

条件n:sn

:

else

:sn+1endcase

SPARKS语言的case语句2.3用SPARKS语言写算法

SPARKS语言的循环语句while

条件

do

SrepeatloopSuntil

条件

repeatfor

变量

初值

to

终值

by

变量增值

do

Srepeat2.3用SPARKS语言写算法

exit

转到含有exit的最内层循环语句后面的第一条语句

goto

标号

cycle

结束本次循环

returnstop2.3用SPARKS语言写算法

SPARKS语言的函数(过程)procedureNAME(<参数列表>)

<说明部分>Sreturn(<表达式>)endNAME函数名,通常用大写字母说明参数的数据类型和函数中使用的变量parameters形式参数global全局变量local局部变量函数的语句部分

SPARKS语言的输入、输出：

read（参数表）；print