1.决定算法复杂度的两个因素 ①问题实例大小 ②实例的具体情况(数据出现的顺序及概率) 2.三种复杂度的定义 本课程重点讨论时间复杂度 3.用三个表说明算法复杂度的重要性(p2-3 4.O与Ω的定义 运算规则:O(f+g)=O(max{f,g}),O(Kf)=O(f) 5.最佳算法的概念定义 6.按算法复杂度对问题分类(cp6) 7.复杂度函数中的常量因子不可忽视(cp6) 第二节算法分析 、评价分析算法的指标(标准)见p5-7略讲 二、复杂度的具体分析指标 1.基本运算次数 2.问题规模量化 3.平均工作量与最坏情况工作量 空间与此类似 第三节复杂度分析 如何具体确定一个完整算法的时间复杂度 1.问题实例大小的量化 2.基本运算的选择 3.分析构成算法各种成分执行时所需工作量 4.利用大○规则求总和 、举例进一步剖析讲解 、用一次课时间补充递推关系的差分解法,内容详见第六节(补充)。 第四节展开法 、如何由具体问题的算法得到形如下式的递归方程 介绍解递归方程maTn+d(n) n> 勺展开法 (举例见第五节) 例1218Ta2Tn-1+1 用母函数法解(定义T=0) n>11．决定算法复杂度的两个因素 ① 问题实例大小 ② 实例的具体情况（数据出现的顺序及概率） 2．三种复杂度的定义 本课程重点讨论时间复杂度 3． 用三个表说明算法复杂度的重要性（p2-3） 4．○与W 的定义 运算规则：○(f+g)=○(max{f,g}), ○(Kf)=○(f) 5．最佳算法的概念定义（cp6） 6．按算法复杂度对问题分类（cp6） 7．复杂度函数中的常量因子不可忽视（cp6） 第二节 算法分析 一、评价分析算法的指标（标准）见 p5-7 略讲 二、复杂度的具体分析指标 1．基本运算次数 2．问题规模量化 3．平均工作量与最坏情况工作量 空间与此类似。 第三节 复杂度分析 一、如何具体确定一个完整算法的时间复杂度 1．问题实例大小的量化 2．基本运算的选择 3．分析构成算法各种成分执行时所需工作量 4．利用大○规则求总和 二、举例进一步剖析讲解 三、用一次课时间补充递推关系的差分解法，内容详见第六节（补充）。 第四节 展开法 一、如何由具体问题的算法得到形如下式的递归方程 二、介绍解递归方程 Tn= ïî ï í ì + > = aT d(n) n 1 c n 1 b n 的展开法 （举例见第五节） 例 12 p18 T n = î í ì + > = - 2T 1 n 1 1 n 1 n 1 用母函数法解（定义 T0=0）