《北京大学屈婉玲算法设计与分析最新课件06资料》由会员分享，可在线阅读，更多相关《北京大学屈婉玲算法设计与分析最新课件06资料（78页珍藏版）》请在金锄头文库上搜索。
1、第第6章算法分析与章算法分析与 问题的计算复杂度问题的计算复杂度 6.1 平凡下界平凡下界 6.2 直接计数求解该问题所需要的最少运算直接计数求解该问题所需要的最少运算6.2 直接计数求解该问题所需要的最少运算直接计数求解该问题所需要的最少运算 6.3 决策树决策树 6.4 检索算法的时间复杂度分析检索算法的时间复杂度分析 6 5 排序算法的时间复杂度分析排序算法的时间复杂度分析6.5 排序算法的时间复杂度分析排序算法的时间复杂度分析 6.6 选择算法的时间复杂度分析选择算法的时间复杂度分析 算法正确性算法正确性 正确性正确性 在给定有效输入后在给定有效输入后, 算法经过有限时间的算法经过有限
2、时间的正确性正确性 在给定有效输入后在给定有效输入后, 算法经过有限时间的算法经过有限时间的 计算并产生正确的答案计算并产生正确的答案, 就称算法是正确的就称算法是正确的. 正确性证明的内容正确性证明的内容： 正确性证明的内容正确性证明的内容： 方法的正确性证明方法的正确性证明算法思路的正确性算法思路的正确性. 证明证明 系列与算法的工作对象有关的引理系列与算法的工作对象有关的引理定理以定理以一一系列与算法的工作对象有关的引理系列与算法的工作对象有关的引理、定理以定理以 及公式及公式. 程序的正确性证明程序的正确性证明证明所给出的系列指证明所给出的系列指 程序的正确性证明程序的正确性证明证明所
3、给出的证明所给出的一一系列指系列指 令确实做了所要求的工作令确实做了所要求的工作. 2 工作量工作量时间复杂性分析时间复杂性分析 计量工作量的标准: 对于给定问题,该算法所执行计量工作量的标准: 对于给定问题,该算法所执行 的基本运算的次数的基本运算的次数的基本运算的次数的基本运算的次数. 基本运算的选择：根据问题选择适当的基本运算 . 基本运算的选择：根据问题选择适当的基本运算 问题基本运算 在表中查找 问题基本运算 在表中查找x比较比较 实矩阵相乘实数乘法实矩阵相乘实数乘法 排序排序比比较较排序排序较较 遍历二叉树置指针遍历二叉树置指针 两种时间复杂性两种时间复杂性: 最坏情况下的复杂性最
4、坏情况下的复杂性W(n) 平均情况下的复杂性平均情况下的复杂性A( ) 3 平均情况下的复杂性平均情况下的复杂性A(n) 占用空间占用空间空间复杂性分析空间复杂性分析 两种占用两种占用 存储程序和输入数据的空间存储程序和输入数据的空间存储程序和输入数据的空间存储程序和输入数据的空间 存储中间结果或操作单元所占用空间存储中间结果或操作单元所占用空间额外空间额外空间 影响空间的主要因素影响空间的主要因素： 影响空间的主要因素影响空间的主要因素： 存储程序的空间一般是常数存储程序的空间一般是常数(和输入规模无关和输入规模无关) 输入数据空间为输入规模输入数据空间为输入规模 O( ) 输入数据空间为输
5、入规模输入数据空间为输入规模 O(n) 空间复杂性考虑的是额外空间的大小空间复杂性考虑的是额外空间的大小 额外空间相对于输入规模是常数额外空间相对于输入规模是常数 称为称为原地工作的原地工作的 额外空间相对于输入规模是常数额外空间相对于输入规模是常数, 称为称为原地工作的原地工作的 算法算法. 两种空间复杂性两种空间复杂性: 最坏情况下的复杂性最坏情况下的复杂性 4 平均情况下的复杂性平均情况下的复杂性. 简单性简单性 含义：算法简单，程序结构简单含义：算法简单，程序结构简单. 好处：容易验证正确性 便于程序调试 好处：容易验证正确性 便于程序调试 简单的算法效率不一定高简单的算法效率不一定高
6、. 要在保证一定效率的前提下力 求得到简单的算法 要在保证一定效率的前提下力 求得到简单的算法 5 基于时间的最优性基于时间的最优性 含义：指求解某问题算法类中效率最高的算法含义：指求解某问题算法类中效率最高的算法 两种最优性两种最优性 最坏情况下最优最坏情况下最优：设：设 A 是解某个问题的算法是解某个问题的算法, 如果在解这如果在解这, 个问题的算法类中没有其它算法在最坏情况下的时间复杂 性比 个问题的算法类中没有其它算法在最坏情况下的时间复杂 性比 A 在最坏情况下的时间复杂性低在最坏情况下的时间复杂性低, 则称则称 A 是解这个问是解这个问 题在最坏情况下的最优算法题在最坏情况下的最优
7、算法题在最坏情况下的最优算法题在最坏情况下的最优算法. 平均情况下最优平均情况下最优：设：设 A 是解某个问题的算法是解某个问题的算法, 如果在解这如果在解这 个问题的算法类中没有其它算法在平均情况下的时间复杂 性比 个问题的算法类中没有其它算法在平均情况下的时间复杂 性比 A 在平均情况下的时间复杂性低在平均情况下的时间复杂性低, 则称则称 A 是解这个问是解这个问 题在平均情况下的最优算法题在平均情况下的最优算法题在平均情况下的最优算法题在平均情况下的最优算法 6 寻找最优算法的途径寻找最优算法的途径 (1) 设计算法设计算法A, 求求W(n)，得到算法类最坏情况下时间复杂度，得到算法类最
8、坏情况下时间复杂度 的一个上界的一个上界 (2) 寻找函数寻找函数F(n), 使得对任何算法都存在一个规模为使得对任何算法都存在一个规模为 n 的输的输( )( ), 入并且该算法在这个输入下至少要做入并且该算法在这个输入下至少要做F(n)次基本运算，得次基本运算，得 到该算到该算法法类最坏情况类最坏情况下下时时间间复杂度复杂度的一的一个个下下界界到该算类最坏情况时复杂度个界到该算类最坏情况时复杂度个界 (3) 如果如果W(n)=F(n)或或W(n)= (F(n), 则则A是最优的是最优的. (4) 如果如果W( )F( ) A不是最优的或者不是最优的或者F( )的下界过低的下界过低(4) 如
9、果如果W(n)F(n), A不是最优的或者不是最优的或者F(n)的下界过低的下界过低. 改进改进A或设计新算法或设计新算法A使得使得W(n)F(n). 重复以上两步重复以上两步, 最终得到最终得到W(n) = F(n) 或者或者W(n) = (F(n) 7 ,( )( )( )( ) 6.1 平凡下界平凡下界平凡下界平凡下界 算法的输入规模和输出规模是它的平凡下界算法的输入规模和输出规模是它的平凡下界 例例1 问题问题：写出所有的写出所有的n阶置换阶置换问题问题：写出所有的写出所有的n阶置换阶置换 求解的时间复杂度下界为求解的时间复杂度下界为 (n!) 例例2例例2 问题：求问题：求n次实系数
10、多项式多项式在给定次实系数多项式多项式在给定x的值的值 求解的时间复杂度下界为求解的时间复杂度下界为 ( )求解的时间复杂度下界为求解的时间复杂度下界为 (n) 例例3 问题：求两个问题：求两个n n 矩阵的乘积 求解的时间复杂度下界是 矩阵的乘积 求解的时间复杂度下界是 (n2) 6.2 直接计数最少运算数直接计数最少运算数 例例4 找最大找最大 算法算法 Findmax 输入 数组输入 数组L, 项数项数 n 1 输出输出 L中的最大项中的最大项MAX 1. MAXL(1); i2;1. MAXL(1); i2; 2. while i n do 3if MAXn then j0 分析：设分
11、析：设 x 在在L中每个位置和空隙的概率都是中每个位置和空隙的概率都是1/(2n+1) W(n)=n A(n)=(1+2+.+n)+n(n+1)/(2n+1) 3n/4. 12 二分捡索最坏时间复杂度二分捡索最坏时间复杂度 定理定理1 W(n) = logn + 1 n 1 证 对证 对n归纳归纳 n=1时时, 左左= W(1)=1, 右右 = log 1 +1 = 1. ) (1)(+ += =WnW n 假设对一切假设对一切k, 1 k 1 do 3.k FLAG 13. k FLAG1 4. FLAG 1 5. for j=1 to k doj 6. if L(j) L(j+1) the
12、n do 7. L(j) L(j+1) 8. FLAG j 20 实例实例 5 3 2 6 9 1 4 8 7 3 2 5 6 1 4 8 79 23 5 1 4 6 78 9 2314567892 3 1 4 5 6 7 8 9 2 13 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 特点特点交换发生在相邻素之间交换发生在相邻素之间特点特点：交换发生在相邻交换发生在相邻元元素之间素之间 21 置换与逆序置换与逆序 逆序 令逆序 令L=1,2,.,n, 排序的任何输入为排序的任何输入为L上的置换上的置换. 在置在置 换换中若中若i j 但但则称则称 () 为该置换的个逆序为该置换
13、的个逆序换换a1a2.an中若中若iaj, 则称则称 (ai,aj) 为该置换的为该置换的一一个逆序个逆序 . 序序序序个个 逆逆序序序序列 在列 在 i 右边，并且小于右边，并且小于i 的元素的元素个个数记作数记作bi, i=1, 2,n. ( b1, b2, , bn) 称为置换的逆序序列称为置换的逆序序列 实例 置换 实例 置换3 1 6 5 8 7 2 4 逆序序列为逆序序列为(0, 0, 2, 0, 2, 3, 2, 3) 22 逆逆序序列的性质序序列的性质序序列的性质序序列的性质 b1=0; b2=0,1; ; bn= 0,1, , n-1 总共总共个不同的逆序序列个不同的逆序序列
14、 总共总共n!个不同的逆序序列个不同的逆序序列 置换与它的逆序序列构成一一对应置换与它的逆序序列构成一一对应 逆序数：置换中的逆序总数逆序数：置换中的逆序总数 b1+ b2+ + bn 12n 实例 置换 实例 置换3 1 6 5 8 7 2 4 逆序序列为逆序序列为( 0, 0, 2, 0, 2, 3, 2, 3 ) 逆序数逆序数12逆序数逆序数12 23 冒泡排序算法复杂度分析冒泡排序算法复杂度分析 最坏情况分析：最坏情况分析：W(n)=O(n2), 至多巡回至多巡回O(n)次，每次次，每次O(n). 对换只发生在相邻元素之间，每次相邻元素交换只消除对换只发生在相邻元素之间，每次相邻元素交
15、换只消除1 个逆序，比较次数不少于逆序数，最大逆序数个逆序，比较次数不少于逆序数，最大逆序数 n(n 1)/2， 于是于是W(n)= (n2). 平均情况平均情况：设各种输入是等可能的设各种输入是等可能的，置换置换 的的逆序序列是逆序序列是平均情况平均情况：设各种输入是等可能的设各种输入是等可能的，置换置换 的的逆序序列是逆序序列是 (b1, b2, , bn), 置换 的逆序序列为置换 的逆序序列为 (0 b1, 1 b2, , n 1 bn)， ， 与与 的逆序数的逆序数之之和为和为 n(n 1)/2. n!个个置置换分成换分成 n) 与与的逆序数和为的逆序数和为()个换分成个换分成 n!/2个组，每组逆序之和为个组，每组逆序之和为 n(n 1)/2. 平均逆序数平均逆序数 n(n 1)/4，平均的交换次数为平均的交换次数为 n(n 1)/4. 平均逆序数平均逆序数()/ ，平均的交换次数为平均的交换次数为()/ . 冒泡排序的最坏和平均复杂性均为冒泡排序的最坏和平均复杂性均为 (n2) 24 快速排序与二分归并排序快速排序与二分归并排序 快速排序快速排序 最坏情况最坏情况 O(n2) 平
