查找排序 程序设计专题
程序设计专题 查找/排序
学习目标 ■了解算法效率的度量方法和大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次