算法分析与设计教程文件.doc

《算法分析与设计教程文件.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、__________________________________________________第一章什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。算法的三个要素 1).数据:运算序列中作为运算对象和结果的数据. 2).运算:运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移:运算序列中的控制和转移.算法分类从解法上：数值型算法:算法中的基本运算为算术运算；非数值型算法:算法中的基本

2、运算为逻辑运算.从处理方式上：串行算法:串行计算机上执行的算法；并行算法:并行计算机上执行的算法算法的五个重要的特性（1）有穷性：在有穷步之后结束。 （2）确定性：无二义性。（3）可行性：可通过基本运算有限次执行来实现。 （4）有输入表示存在数据处理 （5）有输出伪代码 程序设计语言（PDL），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言（例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。____________________________________________________

3、________________________________________________特点：1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2)以自然语言的自由语法描述了处理过程；3)数据声明应该既包括简单的也包括复杂的数据结构；4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n阶方阵的相加C=A+B的算法如下，分析其时间复杂度。 #defineMAX20//定义最大的方阶 voidmatrixadd(intn,intA[MAX][MAX], intB[MAX][MAX],in

4、tC[MAX][MAX]) {inti,j; for(i=0;i

5、+(m-1)=m(m-1)/2，并满足s=m(m-1)/2

6、n,0)的时间复杂度为T(n)，则fun(a,n,k)的执行时间为T1(n,k)，由fun()算法可知： T1(n,k)=n当k=n-1时T1(n,k)=(n-k)+T1(n,k+1)其他情况则： T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2) 　　=…=n+(n-1)+…+2+T1(n,n-1) 　　=n+(n-1)+…__________________________________________________________________________________________

7、__________+2+n 　　=O(n2)所以调用fun(a,n,0)的时间复杂度为O(n2)。估计如下二重循环算法在最坏情况下时间复杂性T(n)的阶。fori:=1tondo forj:=1toido {s1,s2,s3,s4};s1,s2,s3,s4为单一赋值语句 分析:内循环体只需O(1)时间，故 内循环共需外循环共需渐进分析 时间复杂性渐进阶分析的规则：(最坏情况) 1).赋值，比较，算术运算，逻辑运算，读写单个变量（常量）只需1单位时间 2).执行条件语句ifcthenS1elseS2的时间为TC+max(TS1,

8、TS2). 3).选择语句caseAofa1:s1；a2:s2；...；am:sm 需要的时间为max（TS1,TS2,...,TSm）. 4).访问数组的单个分量或纪录的单个域需要一个单位时间. 5).执行for循环语句的时间=执行循环体时间*循环次数. 6)