数据结构1-2算法分析课件

2.算法分析

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。123haha()

{ /*onlyajoke,donothing.*/

}

main()

{ printf("请稍等...您将知道世界的未日...");

while(1)

haha();

}算法的五个重要的特性：

(1)有穷性：在有穷步之后结束，每一步都在有穷时间内完成。5算法的五个重要的特性：

(1)有穷性：在有穷步之后结束，每一步都在有穷时间内完成。(2)确定性：每一条指令必须有明确的含义，算法只有唯一的一条执行路径。

(3)可行性：可通过基本运算有限次执行来实现。6

输入：有0个或多个输入；

输出：有一个或多个输出；getsum(intnum)

{ inti,sum=0;

for(i=1;i<=num;i++)

sum+=i;

} 算法的五个重要的特性：

无输出的算法没有任何意义!7考虑下列两段描述：(1)描述一

voidexam1() { n＝2; while(n%2＝＝0) n＝n+2; printf("%d\n",n); }华中科大考研题

(2)描述二

voidexam2() { y=0; x=5/y; printf(“%d,%d\n”,x,y); }

这两段描述是否满足算法的特征,若不满足试问它们违反了哪些特征？9解：(1)算法是一个死循环,违反了算法的有穷性特征。(2)算法包含除零错误,违反了算法的可行性特征。10算法的描述编写算法时，可采用自然语言、流程图、计算机语言描述。欧几里德算法mnr例：欧几里德算法——辗转相除法求两个自然数m

和n

的最大公约数11算法的描述方法——自然语言

优点：容易理解缺点：冗长、二义性、不易转成程序13N开始输入m和n

r=m%nr=0m=n；n=r输出n结束Y例：欧几里德算法算法的描述方法——流程图

优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次14intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}程序设计语言例：欧几里德算法算法的描述方法——程序设计语言（伪代码）15伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解算法的描述方法——伪代码

17（1）正确性（Correctness）

无语法错误

无逻辑错误算法设计的要求：（2）可读性（Readability）

晦涩难懂的程序易隐藏错误难以调试维护18（3）健壮性（Robustness）

输入数据非法时，不会产生莫名其妙的错误。算法设计的要求：（4）效率与低存储的要求19算法设计的步骤：问题描述模型的选择

算法设计和正确性证明

算法的程序实现

算法分析21算法一算法二在三个整数中求最大者max(inta,intb,intc)

{if(a>b)

if(a>c)returna;

elsereturnc;

else

if(b>c)returnb;

elsereturnc;

}/*无需额外存储空间，只需两次比较*/max(inta[3])

{intc,inti;

c=a[0];

for(i=1;i<3;i++)

if(a[i]>c)c=a[i];

returnc;

}

/*需要两个额外的存储空间，两次比较，至少一次赋值*/

/*共需5个整型数空间*/求100个整数中最大者同上的算法难写，难读max(inta[100])

{intc,inti;

c=a[0];

for(i=1;i<100;i++)

if(a[i]>c)c=a[i];

returnc;

}

/*共需102个整型数空间*/效率与存储量分析22算法分析（AlgorithmAnalysis）：对算法所需要的计算机资源——时间和空间进行估算。时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）算法分析23问题规模：输入量的多少基本语句（程序步）：被视为算法基本运算的一般是最深层循环内的语句。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;问题规模：n基本语句：x++算法分析25

在一个算法中,进行基本运算的次数越少,其运行时间也就相对地越少；基本运算次数越多,其运行时间也就相对地越多。所以,通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数。

算法中基本运算次数T(n)是问题规模n的某个函数f(n),记作：

T(n)=O(f(n))26算法的时间复杂度O(1)<O(log2(n))<O(n)<(n2)<O(n3)<O(2n)29

例：

求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。

#defineMAX20/*定义最大的方阶*/voidmatrixadd(intn,intA[MAX][MAX],intB[MAX][MAX],intC[MAX][MAX]){ inti,j; for(i=0;i<n;i++) for(j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j];}30

该算法中的基本运算是两重循环中最深层的语句C[i][j]=A[i][j]+B[i][j],分析它的频度,即：

T(n)==O(n2)31例：分析以下算法的时间复杂度。

intfun(intn){inti,j,k,s;s=0;for(i=0;i<=n;i++)for(j=0;j<=i;j++) for(k=0;k<=j;k++)s++;return(s);}基本语句或基本操作32

解：该算法的基本操作是语句s++,其频度：

T(n)==O(n3)则该算法的时间复杂度为O(n3)。33最好情况：出现概率较大时分析最差情况：实时系统平均情况：已知输入数据是如何分布的，通常假设等概率分布结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。1.4算法及算法分析最好情况、最坏情况、平均情况34Voidbubble_sort(inta[],intn){//起泡排序：将a中整数序列按照升序重新排列For(i=n-1,change=TRUE;i>=1&&change;--i){ change=FALSE; for(j=0;j<i;j++) if(a[j]>a[j+1]) {a[j]a[i+1];change=TRUE} }}35分析：输入集合升序：基本操作次数为0输入集合逆序：操作次数为：n(n-1)/2T(n)==4·=O(n2)36分析下面语句的时间复杂度：i=1; while(i<=n) i=i*2;分析：37设语句i=i*2的语句频度为f(n)，则有2f（n）<=n，即f（n）<=log2n，所以该程序段的时间复杂度T（n）=O(log2n)。分析下面语句的执行次数：i=0;s=0;n=100;do i=i+1; s=s+10*iwhile(NOT((i<n)AND(s<n)));分析：38该程序段中，循环语句的执行次数为4（这时i=4，s=100），do循环中先执行循环体，后判断条件，直到条件为真时退出循环。算法空间复杂度度量一个算法一般占用三部分存贮空间算法本身占用输入、输出数据占用：算法运行中临时占用空间（可变部分）算法的空间性能以一个算法运行过程中临时占用的存储空间作为度量标准——算法空间复杂度，记作S(n)=O(f(n))时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。39算法空间复杂度度量若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。4041基本操作的实现：

本书约定：常量的定义：

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2数据元素类型约定为：ElemType

typedefintStatus;//函数类型，函数结果状态代码41练习：1、有下列运行时间函数,分别写出相应的大O表示的运算时间。(1)T1(n)=1000; (2)T2(n)=n^2+1000n; (3)T3(n)=3n^3+100n^2+n+1;2、分析下面语句的时间复杂度：for(i=1;i<=n;i++) (2)i=1;k=0; for(j=1;j<=i;j++) while(i<=n-1){ s++; k+=10*i; i++;}42解答：2、分析下面语句的时间复杂度：for(i=1;i<=n;i++)