数据结构，算法与程序设计-Read.ppt

算法设计与分析;课程安排;主要参考书目;第1章 算法在计算中的应用;什么是算法？ 为什么要对算法进行研究？ 相对于计算机中使用的其他技术来讲，算法的作用是什么？; 算法的定义;例1：将一列数按非降序进行排列;算法的正确性;为什么要对算法进行研究？;算法相对其他技术的区别;第2章 程序性能;2.1 引论;续;实例长度-输入量;2.2 空间复杂度(Space Complexity) Sp(n);2.2(续);例题2.2;例题2.2(续);例题2.3;例题2.4;例题2.5;小结;2.3 时间复杂度(time complexity)T(n);2.3.2 操作计数;例题2.8 [Polynomial Evaluation];例题2.8 [Polynomial Evaluation];例题2.9 [Ranking];例题2.9（续）;例题2.10 [Rank Sort] ;例题2.11 [Selection Sort] ;最好，最坏和平均情形时间复杂度;最好，最坏和平均情形时间复杂度;例题2.13 [Sequential Search] ;例题2.14 [Insertion into Sorted Array] ;例： 向数组[0:5]=[1,2,6,8,9,11]中插入4，所得到的结果为a[0:6]=[1,2,4,6,8,9,11];例题2.15 [Rank Sort Revisited] ;(续);例题2.15 [Rank Sort Revisited];Rank Sort Revisited;例题2.16 [Selection Sort Revisited] ;例题2.18 [Insertion Sort] ;例题2.18 [Insertion Sort] ;Insertion Sort;2.3.3 Step Count 方法;例题2.19 ;例题2.19 ;Frequency可能不等于Total steps， ;Step table for Program 2.23;例题2.20;例题2.21[Matrix Addition];Step table for Program 2.19;例题2.22[Sequential Search];Step table for Pro2.1—best-case;Step table for Pro2.1—worst-case;2.4渐近分析,符号(О,Ω,Θ);渐近分析(续);2.4渐近分析(续);Can a Algorithm work with large input ?;渐近分析-随n的增加T(n)的增长率;2.4渐近分析(续);渐近分析(续);2.4渐近分析(续);渐近分析(续);2.4渐近分析时用到的一些等式;续;推导规则;推导规则(续);渐近分析例题;续;续;续;续;多项式时间算法;NP-hard 问题;数值比较:1G指令/秒的计算能力;数值比较:1G指令/秒的计算能力;本章作业：