算法设计与分析基础知识.ppt

伪代码的使用（1） 伪代码(Pseudocode) 是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。 书中所用部分伪代码的语法规则 （1）在伪代码中，每一条指令占一行，指令后不跟任何符号（Pascal和C中语句要以分号结尾）； 伪代码的使用（2） （2）使用与结构化程序语言类似的结构，如if- then-else、for、while等；书写上的“缩进” 表示程序中的分支结构。同一模块的语句有相 同的缩进量，次一级模块的语句相对其父模块 缩进量 （3）在伪代码中，变量名和保留字不区分大小 写，这一点和Pascal相同，与C或C++不同； （4）在伪代码中，变量不需声明，但变量局部于特 定过程，不能不加显示的说明就使用全局变量 伪代码的使用（3） （5）数组元素的存取有数组名后跟“[下标]”表 示。例如A[j]指示数组A的第j个元素。符号 “ …”用来指示数组中值的范围。 例：?A[1…j]表示含元素A[1], A[2], … , A[j]的子数组； (6) 赋值语句用符号←表示， 例B[1..n] ←A[1..n] (7) 函数值利用 “return (函数返回值)” 语句 来返回 1.2.1 算法复杂性分析的必要性 排序：将一组杂乱无章的数据排列成一个按元素有序的序列。 排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。在此给出算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象元素序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。 算法分析 待排序的对象个数为 n，该算法的主程序执行n-1趟。 元素比较次数和对象赋值次数与对象元素的初始排列有关。 最好情况下，排序前对象已经按非降序排列，每趟只需与前面的有序对象序列的最后一个对象的元素比较1次，赋值2 次对象，总的元素比较次数为 n-1，对象赋值次数为 2(n-1)。 最坏情况下，第 i 趟时第 i 个对象必须与前面 i-1个对象都做元素比较，并且每做 1 次比较就要做 1 次数据赋值。则总的元素比较次数KCN和对象赋值次数RMN 选择排序算法（p8） 输入：n个元素的数组A[1..n] 输出：按非降序排列的数组A[1..n] 1. for i←1 to n-1 2. k←i 3. for j ←i+1 to n 4. if A[j]A[k ] then k ←j 5. end for 6. if k≠I then 交换A[i] 与A[k] 7. end for 归并排序 归并，是将两个或两个以上的有序表合并成一个新的有序表。 对象序列 中有两个有序表A[p] …A[q]和A[q+1] …A[r]。它们可合并成一个有序表，存于另一对象序列B中，然后再放入A[p] …A[r]中。 这种归并方法称为2-路归并 (2-way merging)。 其基本思想是：设两个有序表A[p] …A[q]和A[q+1] …A[r]的对象个数(表长)分别为 n1和 n2，变量 p和q分别是两表=当前检测指针。设表B是归并后的新有序表，变量 k 是它的当前存放指针。 当 p 和q都在两个表的表长内变化时，根据A[p]与A[q]的元素的大小，依次把元素小的对象排放到新表B[k]中； 当 p 与 q中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表B[k]中。 合并两个已排序的表（MERGE)（P6) 1.comment:B[p..r]是个辅助数组 2.s←p;t ←q+1;k ←p 3.while s≤q and t≤r 4. if A[s] ≤A[t] then B[k] ←A[s] s ←s+1 7 .else B[k] ←A[t] t ←t+1 end if k ←k+1 end while If s=q+1 then B[k..r] ←A[t..r] else B[k..r] ←A[s..q] end if A[p..r] ←B[p..r]