最新算法分析与设计word版本.doc

《最新算法分析与设计word版本.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、性（1）有穷性：在有穷步之后结束。 （2）确定性：无二义性。（3）可行性：可通过基本运算有限次执行来实现。 （4）有输入表示存在数据处理 （5）有输出伪代码 程序设计语言（PDL），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言（例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。特点：1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2)以自然语言的自由语法描述了处理过程；3)数据声明应该既包括简单的也包括复杂的数据结构；4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两

3、个n阶方阵的相加C=A+B的算法如下，分析其时间复杂度。 #defineMAX20//定义最大的方阶 voidmatrixadd(intn,intA[MAX][MAX], intB[MAX][MAX],intC[MAX][MAX]) {inti,j; for(i=0;i

4、c(intn) {inti=0,s=0; while(s

5、(i=k;i

6、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,TS2). 3).选择语句caseAofa1:s1

7、；a2:s2；...；am:sm 需要的时间为max（TS1,TS2,...,TSm）. 4).访问数组的单个分量或纪录的单个域需要一个单位时间. 5).执行for循环语句的时间=执行循环体时间*循环次数. 6).whilecdos(repeatsuntilc)语句时间=(Tc+Ts)*循环次数. 7).用goto从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8).过程或函数调用语句：对非递归调用，根据调用层次由里向外用规则1-7进行分析； 对递归调用，可建立关于T(n)的递归方程,求解该方程得到T(n).插入排序算法的实现要点：（

8、1）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表