数据结构1-2算法分析

2.算法分析

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。1Step1：寻找鸡蛋。１分钟后仍没找到，打电话给老婆，终于找到。Step2：洗鸡蛋。Step3：打鸡蛋。轻轻磕，用力磕，用大力磕。Step4：清理操作台上的鸡蛋清。Step

5：清理碗中的鸡蛋壳。用筷子夹，用勺子舀，用手抓，成功了（现在知道为什么要洗鸡蛋了吧）。Step6：搅拌。清理脸上、手上和衣服上的鸡蛋清。Step

7：发现碗中的鸡蛋没剩下多少，又拿出两枚，重复２—７Step

8：打火，打不着。还是打不着。怎么打也打不着。Step

9：打电话问老婆。Step

10：拧开气阀，终于打着了。Step

11：擦红花油，简单处理脸部灼伤。Step

12：放油。Step

13：倒掉红花油，重新放入花生油。哎，一字之差！Step

14：等待油热，并幻想老婆吃鸡蛋时被表扬。Step

15：救火，扇子扇，水泼，火越烧越大。Step

16：在浓烟中爬着去找电话。Step

17：在电话旁思考火警电话是１１０、１２０还是１１９。2haha()

{ /*onlyajoke,donothing.*/

}

main()

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

while(1)

haha();

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

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

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

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

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

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

{ inti,sum=0;

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

sum+=i;

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

无输出的算法没有任何意义!5

确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。在相同的条件下，算法对于相同的输入只能得出相同的输出。下面代码有何问题？floataverage(int*a,intnum) /*num为数组a元素个数*/{ inti; doublesum=0;

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

sum+=*(++a);

returnsum/num;

}main(){ intscore[9]={1,2,3,4,5,6,7,8,9};

printf("%f",average(score,9));}6考虑下列两段描述：(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); }

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

和n

的最大公约数9①输入m

和n；②求m除以n的余数r；③若r等于0，则n为最大公约数，算法结束；否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。例：欧几里德算法自然语言算法的描述方法——自然语言

10算法的描述方法——自然语言

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

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

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

15（1）正确性（Correctness）

无语法错误

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

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

输入数据非法时，不会产生莫名其妙的错误。算法设计的要求：（4）效率与低存储的要求17算法设计的目标正确性可使用性（用户友好性）可读性健壮性（很好的容错性）高效率与低存储量需求18算法设计的步骤：问题描述模型的选择

算法设计和正确性证明

算法的程序实现

算法分析19算法一算法二在三个整数中求最大者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个整型数空间*/效率与存储量分析20算法分析（AlgorithmAnalysis）：对算法所需要的计算机资源——时间和空间进行估算。时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）算法分析21同一问题可以采用多种算法实现。如何比较算法执行效率？

算法选用的策略问题的规模：求解的输入量采用的程序语言编译程序的好坏机器执行速度

因此，使用绝对时间单位衡量算法的效率不合适22问题规模：输入量的多少基本语句（程序步）：被视为算法基本运算的一般是最深层循环内的语句。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;问题规模：n基本语句：x++算法分析23

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

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

T(n)=O(f(n))24定理：若A(n)=amnm+am-1nm-1++a1n+a0是一个m次多项式，则A(n)=O(nm)。说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。算法分析算法分析——大O符号25算法的时间复杂度一个没有循环的算法的基本运算次数与问题规模无关：

O（1）常数阶一个只有一重循环的算法的基本运算次数与问题规模呈线性增大关系：

O（n）线性阶26算法的时间复杂度O(1)<O(log2(n))<O(n)<(n2)<O(n3)<O(2n)27

例：

求两个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];}28

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

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

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);}基本语句或基本操作30

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

T(n)==O(n3)则该算法的时间复杂度为O(n3)。31最好情况：出现概率较大时分析最差情况：实时系统平均情况：已知输入数据是如何分布的，通常假设等概率分布结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。1.4算法及算法分析最好情况、最坏情况、平均情况32Voidbubble_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} }}33分析：输入集合升序：基本操作次数为0输入集合逆序：操作次数为：n(n-1)/2T(n)==4·=O(n2)34分析下面语句的时间复杂度：i=1; while(i<=n) i=i*2;分析：35设语句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)));分析：36该程序段中，循环语句的执行次数为4（这时i=4，s=100），do循环中先执行循环体，后判断条件，直到条件为真时退出循环。算法空间复杂度度量一个算法一般占用三部分存贮空间算法本身占用输入、输出数据占用：算法运行中临时占用空间（可变部分）算法的空间性能以一个算法运行过程中临时占用的存储空间作为度量标准——算法空间复杂度，记作S(n)=O(f(n))时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。37算法空间复杂度度量若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。3839基本操作的实现：

本书约定：常量的定义：

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFL