【精品】课件---第1章 绪论-45-1.ppt

关于实验报告 电子版形式 统一实验报告格式 每次实验每人写一个实验报告 每次实验报告在下次上课前提交 实验报告文档命名 个人word文档命名方式例子： “实验1-班级-学号-名字.doc” 按班级统一压缩文档命名方式例子： “实验1-班级.rar” 按班级统一发到指定邮箱，邮件标题例子： “实验1-班级” 每次实验登记“学习登记表”，并一同发送到指定邮箱 实验报告内容要求 问题描述、算法描述、附加了足够注释的程序代码 算法中使用的函数、过程、参数、变量的命名要能表示含义 注意算法格式(层次嵌套、不同功能块之间留空) 实验报告评分标准 文档命名 报告内容是否齐全 报告内容是否正确 如何估算算法的时间复杂度？ 从算法中选取一种对所研究的问题来说执行最频繁的基本操作为原操作, 当问题规模 n 相当大时, 该原操作执行时间占算法总执行时间的绝大部分, 所以, 把该原操作在算法中重复执行的次数 (频度) 作为算法运行时间的衡量准则。 可近似认为：算法的执行时间 与 原操作的频度 成正比 估算时间复杂度时取频度的阶次 时间复杂度 n 问题规模，一般为数据的输入量 算法的时间复杂度 算法中各语句的频度之和T(n) T(n)=O( f(n) ) 大O表示法 时间复杂度 O的含义 存在正的常数c和n0，使得当n ? n0时， 0? T(n) ? c* f(n) 表示随着问题规模 n 的增长, 算法执行时间的增长率和 f(n) 的增长率相同, 称 f(n) 为算法的渐近时间复杂度，简称时间复杂度，即， 当n→∞ 时 T (n) /f(n)→常数 。 常用的时间复杂度频率计数 算法中常用的时间复杂度频率计数有7种: 时间复杂度曲线 O(1)O(log2n)＜O(n)＜O(nlog2n)＜(n2)＜O(n3)＜＜O(2n) 时间复杂度计算步骤 时间复杂度的求法 计算T(n) 从T(n)中推断f(n) 影响算法时间复杂度的因素 问题的规模 输入实例的初态 最坏时间复杂度 定义： 算法在最坏情况下的时间复杂度，即为分析估计算法在最坏情况下执行时间的上界。 空间复杂度度量 存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间 可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过malloc和free命令动态使用的空间 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作. 若所需存储量依赖于特定的输入, 则通常按最坏情况考虑。 数据结构---第1章 绪论 * 通常有两种衡量算法效率的方法: 事后统计法 利用计算机内记时功能，不同算法的程 序可以用一组或多组相同的统计数据区分 事前分析估算法 时间复杂度(渐进时间复杂度) 空间复杂度 缺点：必须执行程序 其它因素掩盖算法本质 O(1)常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型 按时间复杂度由小到大排列的频率表为： 数据结构---第1章 绪论 * [例1] 交换i和j的内容 (1) temp=i; (2) i=j; (3) j=temp; 解：T(n)=3 记作T(n)= O(1) 数据结构---第1章 绪论 * [例2] n?n矩阵相乘的算法语句 for ( i=1; i=n; i++ ) n+1 for (j=1; j=n; j++) n(n+1) { c[i, j]=0; n2 for (k=1; k=n; k++) n2(n+1) c[i, j]=c[i, j]+a[i, k]*b[k, j]; n3 } 解：语句频度 T(n)=2 n3 +3 n2 +