算法分析与设计.docxVIP

第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。 算法的三个要素 数据: 运算序列中作为运算对象和结果的数据. 运算: 运算序列中的各种运算:赋值,算术和逻辑运算 控制和转移: 运算序列中的控制和转移. 算法分类 从解法上：数值型算法:算法中的基本运算为算术运算；非数值型算法:算法中的基本运算为逻辑运算. 从处理方式上：串行算法:串行计算机上执行的算法；并行算法:并行计算机上执行的算法算法的五个重要的特性 有穷性：在有穷步之后结束。 确定性：无二义性。 可行性：可通过基本运算有限次执行来实现。 有输入 表示存在数据处理 有输出伪代码 程序设计语言（PDL），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言 （例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。 特点：1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2)以自然语言的自由语法描述了处理过程；3)数据声明应该既包括简单的也包括复杂的数据结构；4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个 n 阶方阵的相加 C=A+B 的算法如下，分析其时间复杂度。 #define MAX 20 ?n?1?n?1 1 ? ?n?1  n ?n ?n?1  1 ? n * n ? n2 ?i O(1）? O(?i  1) ?O(i) i ?0 j ?0 i ?0 i ?0 n?N O(i) ? O(?N i) ? n N( N ?1)) ? O(N2) nn n n j?1 j?1 i?1  i?1 O( 2 赋值，比较，算术运算，逻辑运算，读写单个变 量（常量）只需 1 单位时间 2). 执行条件语句 if c then S1 else S2 的时间为 TC +max(TS1,TS2). 3). 选择语句 case A of a1: s1；a2: s2；...； am: sm 需要的时间为 max（TS1,TS2 ,..., TSm）. 访问数组的单个分量或纪录的单个域需要一个单位时间. 执行 for 循环语句的时间=执行循环体时间*循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数. 用 goto 从循环体内跳到循环体末或循环后面的语句时,不需额外时间 过程或函数调用语句：对非递归调用，根据调用层次由里向外用规则1-7 进行分析； 对递归调用，可建立关于 T(n)的递归方程,求解该方程得到 T(n). 插入排序算法的实现要点： 【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。 【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。 每个变量都要考虑它的数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。 【关键代码】要考虑直接转换还是需要建立相应的独立函数。对于赋值和下标通常可 以直接转换。一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命令或函数 来实现。 归并排序算法的实现要点： 【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。 参数：序列 A[p…r]的子序列 A[p…q]和 A[q+1…r]，可以表示为区间[p,q],[q,r] 指针（或迭代器）p，q，r：p 指向第一个子序列的首元素，q 指向第二个子序列首元素，r 指向第二个子序列末尾元素之后，单个元素数据长度及比较函数指针。 返回值：无 【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。 每个变量都要考虑它的数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。 【关键代码】要考虑直接转换还是需要建立相应的独立函数 。对于赋值和下标通常可以直接转换。 一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作， 通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。 序列的划分算法的实现要点： 【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树