浙江大学：《计算机辅助设计与图形学》课程教学资源（PPT讲稿）查找、排序

查找排序 程序设计专题

程序设计专题 查找/排序

学习目标 ■了解算法效率的度量方法和大O记法 ■掌握简单的线性查找法和二分查找法 ■掌握简单的选择排序法和冒泡排序法 ■了解分而治之策略,基本掌握归并排序法

学习目标 ◼ 了解算法效率的度量方法和大O记法 ◼ 掌握简单的线性查找法和二分查找法 ◼ 掌握简单的选择排序法和冒泡排序法 ◼ 了解分而治之策略，基本掌握归并排序法

算法效率的度量 算法设计的要求 正确性:算法至少应具有输入/出和加工处理无歧义性、 能正确反映问题的需求、能够得到问题的正确答案。 健壮性:当输入数据不合法时,算法能做出相关处理 而非产生异常或莫名其妙的结果 >时间效率==》高 存储量开销==》低 >可读性∶便于阅读、理解和交流

一、算法效率的度量 ◼ 算法设计的要求 ➢ 正确性：算法至少应具有输入/出和加工处理无歧义性、 能正确反映问题的需求、能够得到问题的正确答案。 ➢ 健壮性：当输入数据不合法时，算法能做出相关处理， 而非产生异常或莫名其妙的结果 ➢ 时间效率 ==》高 ➢ 存储量开销 ==》低 ➢ 可读性：便于阅读、理解和交流

算法效率 ■算法效率的度量方法 事后统计方法(有缺点,较少使用) 事前分析估算方法 ■算法时间复杂度 与高级语言程序执行时间相关的因素 算法采用的策略、方法问题的输入规模 <<输入量的多少 胡机器执行指令的速度<<硬件

一、算法效率 ◼ 算法效率的度量方法 ➢ 事后统计方法（有缺点，较少使用） ➢ 事前分析估算方法 ◼ 算法时间复杂度 ➢ 与高级语言程序执行时间相关的因素 ➢ 算法采用的策略、方法 ➢ 编译产生的代码质量 ➢ 问题的输入规模 ➢ 机器执行指令的速度 << 算法好坏的根本 << 软件 << 输入量的多少 << 硬件

算法效率 ■算法时间复杂度 ntn=100,sum=0,;∥执行1次 for(=1;i<=n;i+)∥/执行n+1次 sum= sum t I ∥|行n次 执行2n+3次 printf(%d",sum);∥.行1次

一、算法效率 ◼ 算法时间复杂度 int n = 100, sum = 0, i; //执行 1 次 for (i = 1; i <= n; i++) //执行 n+1 次 sum = sum + i; //执行 n 次 printf("%d", sum); //执行 1 次 执行 2n+3次

算法效率 ■算法时间复杂度 int n =100. sum ∥|行1次 sum=(n+1)*n/2;∥执行1次 执行2n+3次 printf(%d",sum);∥.行1次

一、算法效率 ◼ 算法时间复杂度 int n = 100, sum; //执行 1 次 sum = (n + 1)*n / 2; //执行 1 次 printf("%d", sum); //执行 1 次 执行 2n+3次

算法效率 ■算法时间复杂度 ti,j,X=0,sum=0,n=100 for(i=1; i<=n; i++) for =1; j<=n; j++) n*n X+t sum=sum X printf( %d", sum)

一、算法效率 ◼ 算法时间复杂度 int i, j, x = 0, sum = 0, n = 100; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { x++; sum = sum + x; } printf("%d", sum); n*n

算法效率 ■算法时间复杂度 不同算法的操作数量对比 120 100 操作数量 000 0 12345678910 输入规模 分析个算法的运行时间→把操作数量与输入规 模关联起来 >s随着n的增加,nn的执行次数也将远远多于 n的执行次数

一、算法效率 ◼ 算法时间复杂度 ➢ 分析一个算法的运行时间 ➔把操作数量与输入规 模关联起来 ➢ s随着n的增加，n*n的执行次数也将远远多于 n的执行次数 输入规模 操 作 数 量 不同算法的操作数量对比

算法时间复杂度分析 选取算法中一种基本/主要的原操作(多数情 况下取自最深层次循环体内的语句) 以其重复执行的次数T(n)衡量算法运行时间 n是算法处理的数据问题的规模

算法时间复杂度分析 ◼ 选取算法中一种基本/主要的原操作（多数情 况下取自最深层次循环体内的语句） ◼ 以其重复执行的次数T(n)衡量算法运行时间 ◼ n是算法处理的数据/问题的规模

算法时间复杂度分析 如果存在某个存在2个常数:c1,c2,和函数fn) ,使得当问题的规模n→无穷大的时候,有: c1*f(n<t(n<c2*f(n) 那么称T(n)和f(n)具有相同的渐进复杂度,记作 T(n=o( fn))

算法时间复杂度分析 如果存在某个存在2个常数：c1, c2，和函数f(n) ，使得当问题的规模n→无穷大的时候，有： c1*f(n) < T(n) < c2*f(n) 那么称T(n) 和f(n)具有相同的渐进复杂度，记作 T(n) = O( f(n) )