算法设计与分析算法分析基础PPT课件.pptx

第2章算法分析基础 2 2算法的渐进分析 2 3最好 最坏和平均情况 2 4非递归算法的分析 2 5递归算法的分析 2 1算法分析的基本概念 2020 1 8 1 2 1算法分析的基本概念 一 算法分析 AlgorithmAnalysis 对算法所需要的两种计算机资源 时间和空间进行估算时间复杂性 TimeComplexity 空间复杂性 SpaceComplexity 二 算法分析的目的 设计算法 设计出复杂性尽可能低的算法选择算法 在多种算法中选择其中复杂性最低者 2020 1 8 2 三 算法分析的两个阶段 1 事前分析 求出该算法的一个时间限界函数 2 事后测试 收集此算法的执行时间和实际占用空间的统计资料 2 1算法分析的基本概念 2020 1 8 3 2 2算法的渐进分析 一 相关概念算法的渐进分析是一种事前估算的方法 是指忽略具体机器 编程语言和编译器的影响 只关注在输入规模增大时算法运行时间的增长趋势 渐进时间复杂性当问题的规模n趋向无穷大时 影响算法效率的重要因素是T n 的数量级 而其他因素仅是使时间复杂度相差常数倍 因此 可以用T n 的数量级 阶 评价算法 时间复杂度T n 的数量级 阶 称为渐进时间复杂性 确定一个算法时间的数量级是十分重要的 它在本质上反映了一个算法所需要的计算时间 2020 1 8 4 语句频度 语句执行的次数算法的语句频度f n f n 语句 i 的执行次数 算法中基本操作重复执行的次数之和算法的执行时间 是所有语句的执行时间之和T n 语句 i 的执行次数 语句的执行时间 假设每条语句执行的时间相等 渐进时间复杂度表示 随着问题规模n的增长 算法执行时间的增长率和算法的语句频度f n 的增长率相同 则可记作 T n O f n 称T n 为算法的 渐近 时间复杂度 2 2算法的渐进分析 2020 1 8 5 2 2算法的渐进分析 二 表示方法1 大O符号 运行时间的上界 定义1 1若存在两个正的常数c和n0 对于任意n n0 都有T n c f n 则称T n O f n 2020 1 8 6 大O符号描述增长率的上限 表示T n 的增长最多像f n 增长的那样快当说一个算法具有O f n 的计算时间时 指的是如果此算法用n值不变的同一类数据在某台机器上运行时 所用的时间总是小于f n 的一个常数倍 所以f n 是计算时间T n 的一个上界函数 T n 的数量级就是f n 典型的增长阶 O 1 O lgn O n O nlgn O n2 O n3 O 2n O n 2 2算法的渐进分析 2020 1 8 7 算术运算 O f n O g n O max f n g n O f m O g n O f m g n O f n O g n O f n g n O cf n O f n 若g n O f n 则O f n O g n O f n 若T n 是关于n的k阶多项式 那么T n O nk 2 2算法的渐进分析 2020 1 8 8 证明 取n0 1 当n n0时 利用T n 的定义和一个简单的不等式 有取c am a0 定理得证 事实上 只要将n0取得足够大 可以证明只要c是比 am 大的任意一个常数 此定理都成立 定理1 1若T n amnm a1n a0是一个m次多项式 则T n O nm 此定理表明 变量n的固定阶数为m的任一多项式 与此多项式的最高阶nm同阶 2 2算法的渐进分析 2020 1 8 9 2 2算法的渐进分析 示例 2020 1 8 10 2 2算法的渐进分析 2020 1 8 11 2 2算法的渐进分析 2020 1 8 12 例 1 假设某算法在输入规模是时为 在某台计算机上实现并完成该算法的时间是秒 现有另一台计算机 其运行速度为第一台的64倍 那么 在这台计算机上用同一算法在秒内能解决规模为多大的问题 关系式 算法语句频度 运行速度 时间 每语句 运行总时间 解 设在新机器上秒内能解决规模为的问题 由于新机器运行速度提高64倍 则运行时间 每语句变为 由关系式 得 解 得 2 2算法的渐进分析 2020 1 8 13 由于此时 新机器的运行速度 每语句为 2 若上述算法改进后 新算法 则在新机器上用秒时间能解决输入规模为多大的问题 代入关系式 得 设在新机器上用t秒时间能解决输入规模为N的问题 则 解 得 2 2算法的渐进分析 思考 以上说明了什么问题 2020 1 8 14 2 大 符号 运行时间的下界 定义1 2若存在两个正的常数c和n0 对于任意n n0 都有T n c g n 则称T n g n 2 2算法的渐进分析 2020 1 8 15 大 符号用来描述增长率的下界也就是说 T n g n 是当输入规模为n时 算法消耗时间的最小值 与大 符号对称 这个下限的阶越高 结果就越有价值 问题的计算时间下界为 f n 则计算时间复杂性为O f n 的算法是最优算法 例如 计算时间复杂性为O nlogn 的排序算法是最优算法 堆排序算法就是最优算法 2 2算法的渐进分析 2020 1 8 16 2020 1 8 17 3 符号 运行时间的准确界 定义1 3若存在三个正的常数c1 c2和n0 对于任意n n0都有c1 f n T n c2 f n 则称T n f n 2 2算法的渐进分析 一个算法的T n f n 意味着该算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的 2020 1 8 18 例 T n 5n2 8n 1当n 1时 5n2 8n 1 5n2 8n n 5n2 9n 5n2 9n2 14n2 O n2 当n 1时 5n2 8n 1 5n2 n2 当n 1时 14n2 5n2 8n 1 5n2则 5n2 8n 1 n2 定理1 2若T n amnm am 1nm 1 a1n a0 am 0 则有T n O nm 且T n nm 因此 有T n nm 2 2算法的渐进分析 2020 1 8 19 解答 当n 1时 3n 1 3n O n 当n 1时 3n 1 3n n 2n n 当n 1时 3n 3n 1 2n 则3n 1 n 例T n 3n 1 求 2 2算法的渐进分析 2020 1 8 20 2 3最好 最坏和平均情况 例 在一维整型数组A n 中顺序查找与给定值k相等的元素 假设该数组中有且仅有一个元素值为k intFind intA intn for i 0 i n i if A i k break returni 2020 1 8 21 1 最坏情况下的时间复杂性Tmax n max T I size I n 2 最好情况下的时间复杂性Tmin n min T I size I n 3 平均情况下的时间复杂性Tavg n 其中I是问题的规模为n的实例 p I 是实例I出现的概率 2 3最好 最坏和平均情况 2020 1 8 22 2 3最好 最坏和平均情况 1 Tmax n max T I size I n O n 2 Tmin n min T I size I n O 1 3 在平均情况下 假设 在数组的每个位置i 0 i n 搜索成功的概率相同 均为1 n 2020 1 8 23 最好情况 出现概率较大时分析最差情况 实时系统平均情况 已知输入数据是如何分布的 通常假设等概率分布 结论 如果问题规模相同 时间代价与输入数据有关 则需要分析最好情况 最坏情况 平均情况 2 3最好 最坏和平均情况 2020 1 8 24 1 建立一个代表算法运行时间的求和表达式 2 用渐进符号表示这个求和表达式 voidadd sum 0 for i 1 i n i for j 1 j n j sum sum i j printf d sum 1n 1n n 1 n21 T n O f n O 2n2 2n 3 O n2 2 4非递归算法的分析 算法分类 非递归算法 递归算法 一种分类方式 2020 1 8 25 1 决定用哪个 或哪些 参数作为算法问题规模的度量可以从问题的描述中得到 2 找出算法中的基本语句通常是最内层循环的循环体 3 检查基本语句的执行次数是否只依赖于问题规模如果基本语句的执行次数还依赖于其他一些特性 则需要分别研究最好情况 最坏情况和平均情况的效率 4 建立基本语句执行次数的求和表达式计算基本语句执行的次数 建立一个代表算法运行时间的求和表达式 5 用渐进符号表示这个求和表达式计算基本语句执行次数的数量级 用大O或 或 符号描述算法增长率的上限 非递归算法分析的一般步骤 2 4非递归算法的分析 2020 1 8 26 2 5递归算法的分析 voidHanoi intn charA charB charC if n 1 printf A C else hanoi n 1 A C B printf A C hanoi n 1 B A C T 1 1 n 1 T n 2 T n 1 1 n 1 一 递推关系式 用于表示第n项与它前一项或几项关系的式子 2020 1 8 27 例 Merge sort排序算法的复杂性递归方程为T n 1 ifn 1T n 2T n 2 n ifn 1 T 1 1 n 1 T n 2 T n 1 1 n 1 例 Hanoi问题 T n 2 5递归算法的分析 二 建立递推关系式 关键 对递归算法时间复杂性的分析 关键是根据递归过程 建立递推关系式 然后求解这个递推关系式 2020 1 8 28 步骤 循环地展开递推关系式 把递推关系式转化为求和表达式 然后可使用求和技术解之 三 递推关系式的求解 扩展递归技术 2 5递归算法的分析 2020 1 8 29 2 5递归算法的分析 求以下递推式的时间复杂性 解 设n 2k 2020