1、算法设计与分析算法分析基础-渐近时间复杂度信息管理学院李季内容提要2022-11-29算法设计与分析2算法分析基础P与NP问题基础递归分治动态规划贪心回溯分支限界算法设计经典策略 分析手段 渐近分析与关键操作 分析结果的表示 渐近表示法与渐近时间复杂度 练习算法与算法问题2022-11-29算法设计与分析3问题编程实现理解问题数学建模数学建模确认算法正确性证明正确性证明分析算法时间复杂度时间复杂度空间复杂度空间复杂度策略选择确定数据结构确定过程结构设计算法表示算法算法问题求解框架渐近表示符号：大O记号、记号、记号、小o记号渐近表示法（渐近时间复杂度）：指出时间函数T的渐近上界或下界2022-1
2、1-29算法设计与分析4渐近时间复杂度算法时间复杂度定义程序步计数关键操作计数T(n)渐近分析渐近时间复杂度如何区分算法运行时间在增如何区分算法运行时间在增长趋势上的差异？长趋势上的差异？渐近表示法度量函数的增长趋势2022-11-29算法设计与分析5分析结果的表示_渐近时间复杂度图示图示定义定义意义意义f(n)=O(g(n)能找到c和n0,使得当nn0时，总有：f(n)cg(n)f(n)在数量级上小于等于g(n)或称g(n)是一个上界f(n)=(g(n)能找到c和n0,使得当nn0时，总有：f(n)cg(n)f(n)在数量级上大于等于g(n)或称g(n)是一个下界f(n)=(g(n)能找到c
3、1,c2和n0,使当nn0时,总有:c1g(n)f(n)c2g(n)f(n)在数量级上等于g(n)或称f,g同阶f(n)=o(g(n)能找到c和n0,使得当nn0时，总有：f(n)cg(n)f(n)在数量级上严格小于g(n)或称f比g低阶f(n)f(n)和和g(n)g(n)是定义在自然数集合上的正函数是定义在自然数集合上的正函数f(n)cg(n)f(n)cg(n)c1g(n)c2g(n)f(n)f(n)cg(n)例：f(n)=10n2+4n+21.有 f(n)=O(n2)因为：当因为：当n5后，后，f(n)10n2+5n 10n2+n2 11n2 2.有 f(n)=O(n3)因为：当因为：当n
4、11后，后，f(n)11n2 n33.有 f(n)=(n2)因为：当因为：当n1后，后，f(n)10n2 由1和2知，f有多个渐近上界，越逼近(紧)的上界对f的刻画越精确 由1和3知，f(n)=(n2)，即f和g=n2同阶因为：当因为：当n5后，后，10n2 f(n)11n22022-11-29算法设计与分析6渐近表示法应用 算法设计关键操作计数(最坏情况下)T(n)渐近分析2022-11-29算法设计与分析7渐近表示法应用/素数判定算法1int Is_sushu(int N)int i;int flag=1;if(N=1)return false;if(N=2)return true;for
5、(i=2;i=N;i+)if(N%i=0)flag=0;break;return flag;主要部分/素数判定算法2int Is_sushu(int N)int i;int flag=1;if(N=1)return false;if(N=2)return true;for(i=2;i=sqrt(N);i+)if(N%i=0)flag=0;break;return flag;主要部分最坏时：最坏时：T1=N关键操作执行次数？关键操作执行次数？关键操作执行次数？关键操作执行次数？最坏时：最坏时：T2=sqrt(N)低阶在增长趋势上比易得时，总有显然1221221T,0)(1/)()()(2n,)(
6、,)(TnTnTnTnTnnTnnT算法算法1 1和和2 2的渐近特性有明的渐近特性有明显的差异显的差异 渐近时间复杂度（asymptotic complexity）这种使用记号大O/小o来渐近表示的算法时间 渐近分析中参考函数g(n)：度量时间T渐近数量级 常见函数如下:分析结果的表示_渐近时间复杂度函数函数测试数量级测试数量级g(n)=1常数级g(n)=logn对数级g(n)=nlogn线性对数级g(n)=n线性级g(n)=n2平方级g(n)=n3立方级g(n)=2n指数级 为什么说：速度为算法之魂 给定条件：给定机器A、机器B和限定时间 B的运算速度是A的100倍 给定时间内机器的关键操
7、作执行能力(运算量)不变 对同一问题有几种不同级别的算法存在：O(n),O(n2),O(2n)计算量相同时，不同算法能解决的问题规模n如下图所示2022-11-29算法设计与分析9速度为算法之魂T(n)计算量计算量(A)n算法110n10,0001000算法2n210,000100算法32n10,00013计算量计算量(B)n1,000,0001000001,000,00010001,000,00019规模变化规模变化n/n100101.46要更快的算法胜于要更快的计算机 求算法渐近时间复杂度的步骤：综合示例：求直接插入排序算法时间复杂度 设对表R中元素进行升序排列，R中元素个数为n2022-
8、11-29算法设计与分析10渐近分析小结分析情况：最好、最坏或平均关键操作计数求和渐近分析算法A分析关键操作渐近时间复杂度void lnsertSort(SeqList R)/对顺序表R中的元素R1.n按升序进行插入排序 int i，j；for(i=2;i=n；i+)/依次插入R2，Rn if(Ri=有序区中元素，则Ri不动 R0=Ri;j=i-1;/R0是哨兵，且是Ri的副本 do /从右向左在有序区R1i-1中查找Ri的插入位置 Rj+1=Rj；j-；/将关键字大于Ri的记录后移 while(R0Rj)；/当Ri Rj 时终止 Rj+1=R0；/Ri插入到正确的位置上 /endif/Ins
9、ertSort 2022-11-29算法设计与分析11直接插入排序算法n-1趟插入关键操作移动关键操作比较关键操作移动主要部分关键操作移动关键操作比较分析关键操作分析关键操作2022-11-29算法设计与分析12直接插入排序算法void lnsertSort(SeqList R)/对顺序表R中的元素R1.n按升序进行插入排序 int i，j；for(i=2;i=n；i+)/依次插入R2，Rn if(Ri=有序区中元素，则Ri不动 R0=Ri;j=i-1;/R0是哨兵，且是Ri的副本 do /从右向左在有序区R1i-1中查找Ri的插入位置 Rj+1=Rj；j-；/将关键字大于Ri的记录后移 wh
10、ile(R0Rj)；/当Ri Rj 时终止 Rj+1=R0；/Ri插入到正确的位置上 /endif/InsertSort 分析特殊情况分析特殊情况关键操作比较最好情况：R正序主要部分只有1个关键操作被执行2022-11-29算法设计与分析13直接插入排序算法void lnsertSort(SeqList R)/对顺序表R中的元素R1.n按升序进行插入排序 int i，j；for(i=2;i=n；i+)/依次插入R2，Rn if(Ri=有序区中元素，则Ri不动 R0=Ri;j=i-1;/R0是哨兵，且是Ri的副本 do /从右向左在有序区R1i-1中查找Ri的插入位置 Rj+1=Rj；j-；/将
11、关键字大于Ri的记录后移 while(R0Rj)；/当Ri Rj 时终止 Rj+1=R0；/Ri插入到正确的位置上 /endif/InsertSort 分析特殊情况分析特殊情况最坏情况：R反序关键操作移动关键操作比较主要部分关键操作移动关键操作移动关键操作比较所有关键操作被执行，第2层循环内的执行次数最高R R初始排列状态初始排列状态最好情况最好情况(正序正序)最坏情况最坏情况(反序反序)无序无序(平均平均)第i趟元素比较次数1i+1(i-2)/2 元素总比较次数 n-1(n+2)(n-1)/2n*n/4第i趟元素移动次数0i+2(i-2)/2元素总移动次数0(n-1)(n+4)/2 n*n/
12、4 2022-11-29算法设计与分析14直接插入排序算法关键操作计数和渐近分析关键操作计数和渐近分析时间复杂度时间复杂度 0(n)O(n*n)O(n*n)渐近分析渐近分析最好情况：最好情况：T(n)=(n-1)+0=O(n)最坏情况：最坏情况：T(n)=(n+2)(n-1)/2+(n-1)(n+4)/2=n2+2n-3=O(n*n)平均情况：平均情况：T(n)n*n/4+n*n/4n*n/2=O(n*n)1.证明：如果f(n)=amnm+am1nm1+a1n+a0是m次多项式，且am0，则f(n)=(nm)。2.求以下算法A的渐近时间复杂度 练习【算法A】矩阵乘法AB=C,A/B/C均为n阶
13、方阵void msqure(int a,int b,int&c)for（i=0;in;i+）for（j=0;jn;j+）cij=0;for（k=0;k2qm/am 时,就有f(n)cnm 得证。练习解答 2.求以下算法A的渐近时间复杂度 如上图所示，求各关键操作执行次数，注意循环嵌套 T=n3+n2(n+1)+n2+n(n+1)+(n+1)=2n3+3n2+2n+1=(n3)练习解答【算法A】矩阵乘法AB=C,A/B/C均为n阶方阵void msqure(int a,int b,int&c)for（i=0;in;i+）/n+1 for（j=0;jn;j+）/n(n+1)cij=0;/n2 fo
14、r（k=0;k5后，后，f(n)=10n2+5n=10n2+n2 1后，后，f(n)=0.5n+n 1.5后，后，f(n)1.5n=1时，总有 f(n)=10n2例 f(n)=2n+3=(n)因为n=1时，总有 f(n)=2n 渐近表示法(补充)f(n)f(n)和和g(n)g(n)是定义在自然数集合上的正函数是定义在自然数集合上的正函数记号定义如果存在正常数c1，c2和n0，使得当nn0时，有c1 g(n)f(n)c2g(n)，则记做f(n)=(g(n)。例f(n)=2n+3=(n)，即2n+3(n)例f(n)=10n2+4n+2=(n2)渐近表示法(补充)f(n)f(n)和和g(n)g(n)
15、是定义在自然数集合上的正函数是定义在自然数集合上的正函数 渐近表示法(补充)根据大O的定义，容易证明以下运算规则：(1)O(f)+O(g)=O(max(f,g)(2)O(f+g)=O(f)+O(g)(3)O(fg)=O(f)O(g)(4)如果g=O(f)，则O(f)+O(g)=O(f)(5)O(Cf)=O(f)，其中C是一个正的常数(6)f=O(f)(1)(1)和和(2)(2)表明：时间函数表明：时间函数T T的的增长增长趋势主要由高阶项决定趋势主要由高阶项决定(5)(5)表明：时间函数表明：时间函数T T的的增长增长趋势与高阶项的系数无关趋势与高阶项的系数无关f(n)f(n)和和g(n)g(n)是定义在自然数集合上的正函数是定义在自然数集合上的正函数
