ch2(算法简介)

《ch2(算法简介)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2021/7/20数据结构1第2章算法2.1什么是算法（algorithm）？1、定义算法：是指建立在数据结构基础上的、求解问题的一系列确切的步骤。2021/7/20数据结构2（1）有穷性:经过了有限步骤后，该算法一定会终止。（2）确定性:算法中的每一条指令都必须是清楚无二义的,对于相同的输入有相同的输出。（3）输入:一个算法有零个或多个由外界提供的量。（4）输出:一个算法产生一个或多个输出。（5）有效性（可行性）:算法是可行的，即算法中描述的操作都是可以通过已实现的基本运算的执行来完成，每种运算至少在原理上能由人用纸和笔在有限的时间内完成。2、算法的

2、特性2021/7/20数据结构3(1)自然语言:较为灵活，但不够严谨；(2)计算机语言:严格，但灵活性不足。(3)伪语言（类语言）3、算法的描述2021/7/20数据结构4例2.1给定两个正整数m，n（设nm），求其最大公因子。用自然语言描述算法：（1）比较m，n，如果n

3、：if(m小于n)step2：交换n和m；step3：LOOPstep4：以n除m，余数为r;step5：if(r等于0)执行step8;step6：m←n;n←r;step7：ENDLOOPstep8：输出n;2021/7/20数据结构6用C语言实现算法：intGreatestCommonFactor(intm,intn){intr;if(m0&&n>0){while(1){r=m%n;if(0==r)returnn;m=n;n=r;}}return-1;//n或m不是正整数}

4、2021/7/20数据结构74、算法评价：算法和数据结构密切相关。正确性：是指算法是否正确，特别要注意对边界条件的检测；可读性：好是指有助于人们对算法的理解；健壮性：指算法运行时无论是正确的输入或错误的输入,算法都应给出正确的反应；2021/7/20数据结构8（1）时间性能：指运行算法所需的时间的度量。（2）空间性能：指运行算法所需要的辅助空间的规模。2.2算法分析2021/7/20数据结构91、时间频度一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。n是问题的规模。设有以下三个程序段：A:{x++;}（最大执行次数为1）B:for(i

5、=1;i<=n;i++)(第一条语句最大执行次数为n+1){x++;}(第二条语句最大执行次数为n)（总次数2n+1）C:①for(i=1;i<=n;i++)(执行次为n+1)②for(j=1;j<=n;j++)(执行次数为n*(n+1))③{x++;s+=x;}(执行次数为n2)（总次数2n2+2n+1）2.2.1算法时间效率的分析2、时间复杂度（渐进时间复杂度）：在数据规模n趋向无穷大时，语句频度T(n)的数量级。记作：T(n)=O(f(n))f(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。2021/7/20数据结

6、构102021/7/20数据结构11常见时间复杂度从好到坏的级别依次是：O(1)

7、2n3+3n2+2n+1，故时间复杂度为O(n3)。①n+1②n(n+1)③n2④n2(n+1)⑤n3⑥n22021/7/20数据结构13例2：算法如下：sum(intn){inti,j,sum=0;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++)p*=j;sum+=p;}return(sum);}“p*=j;”的执行频度为：1+2+3+…+n=n(n+1)/2,所以其时间复杂度是O(n2)。2021/7/20数据结构142021/7/20数据结构15例4：递归算法intfac(intn){if(n<=1)return1;

8、elsereturnn*fac(n-1);}2021/7/20数据结构16例4：递归算法int