第9章复杂度及其分析 本章主要介绍下列内容(教材第一章) 1.算法的复杂度 2.算法分析 3.复杂度分析 4.展开法 5.母函数法 6.差分法 课时分配:第1、2节三个学时,第3、4节三个学时,第5、6节共三个学时 重点、难点:算法复杂度分析的步骤、递归算法分析及递归方程解法 第一节算法的复杂度 算法 1.介绍有关统计数据(曹书p1引言) 2.算法的通俗定义 (一个)算法是由有限个指令(规则)组成的有序集合(序列)。这些指令确定了解 决某一问题的一个运算序列。 3.算法的五大特征 ①有穷性 ③能行性 ④输入 ⑤输出 4.求最大公因数的文字算法和高级语言算法。Cp2 5.算法与过程、程序的区别。Cp2 (有穷于无穷,描述多样性与执行多样性) 6.问题、问题实例及与算法运行的关系。pl 、算法设计和算法分析的步骤cp3 1.问题的陈述 2.模型的选择或拟制 3.算法设计和正确性证明 4.算法的程序实现 5.算法分析 三、评价算法的标准(p1)(详见1.2算法分析) 1.正确(算法己隐含该条) 2.易理解、易编程(上机实现)、易修改、可扩展 3.高效(节省时间与空间) 2、3条的辩证关系,谁放在首位,视具体情况而定。(p1,p2) 四、算法复杂度定义第 9 章 复杂度及其分析 本章主要介绍下列内容（教材第一章） 1. 算法的复杂度 2. 算法分析 3. 复杂度分析 4. 展开法 5. 母函数法 6. 差分法 课时分配：第 1、2 节三个学时，第 3、4 节三个学时，第 5、6 节共三个学时 重点、难点：算法复杂度分析的步骤、递归算法分析及递归方程解法 第一节 算法的复杂度 一、算法 1. 介绍有关统计数据（曹书 p1 引言） 2. 算法的通俗定义 （一个）算法是由有限个指令（规则）组成的有序集合（序列）。这些指令确定了解 决某一问题的一个运算序列。 3. 算法的五大特征 ① 有穷性 ② 确定性 ③ 能行性 ④ 输入 ⑤ 输出 4.求最大公因数的文字算法和高级语言算法。Cp2 5.算法与过程、程序的区别。Cp2 (有穷于无穷，描述多样性与执行多样性) 6.问题、问题实例及与算法运行的关系。p1 二、算法设计和算法分析的步骤 cp3 1.问题的陈述 2.模型的选择或拟制 3.算法设计和正确性证明 4.算法的程序实现 5.算法分析 三、评价算法的标准（p1）（详见 1.2 算法分析） 1．正确（算法已隐含该条） 2．易理解、易编程（上机实现）、易修改、可扩展 3．高效（节省时间与空间） 2、3 条的辩证关系，谁放在首位，视具体情况而定。（p1,p2） 四、算法复杂度定义