(
课件网) 第14课 算法效率比一比 授课人：曾老师 第四单元 发挥算法的优势 学习目标 知道解决同一个问题可以有不同的算法，不同的算法具有不同的效率。 1 通过实例比较和算法分析，了解算法执行的关键步骤和执行次数，体会算法存在的效率差异。 2 情境思考 课堂导入 一堆物体摆放如下图所示，要统计有多少个，你能想到哪些方法？ 学习活动 一 用不同方法统计物体数量 三 感受不同算法的运算效率 二 累加运算的效率分析 学习活动 学习活动一：用不同方法统计物体数量 学习活动1：用不同方法统计物体数量 第一种算法：把物体逐层进行累加 通过数一数每层的物体个数，发现其中的变化规律。 物体共 10 层，从上到下，每层分别是 1 至 10 个。 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55 学习活动1：用不同方法统计物体数量 第二种算法：通过求平行四边形中物体的个数来计算 利用正反放置的两个梯形组成平行四边形 平行四边形中物体的个数 = 每层个数 × 层数 =（1+10）×10=110 个 梯形中物体个数 = 平行四边形中物体的个数 ÷2 = 110÷2 = 55 个 累加之和 = ( 第一个数 + 最后一个数 ) × 数的总个数 ÷2 学习活动二：累加运算的效率分析 学习活动2：累加运算的效率分析 通过比较发现： 算法1简单直观，易于理解；算法2所用的步数较少，计算起来更快。 算法一 算法二 解决同一个问题时，不同的算法会有不同的步骤，也存在不同的效率。 学习活动2：累加运算的效率分析 解决某个问题可能会有多种不同的算法，如何评价算法的“好”与“差”呢 学习活动2：累加运算的效率分析 通常，用计算机解决问题时会用以下两种方法来比较算法的效率： 一是比较算法运行所需要的时间。 二是比较算法运行时所需的步数或者占用的资源。 衡量计算机在运行程序时的效率，没有统一的标准，通常选择只比较其中的一个方面。 下面主要从时间上来进行分析。 学习活动2：累加运算的效率分析 大家听过数学家高斯小时候计算“1+2+3+…+100”的故事吧？ 高斯使用第二种算法很快给出了答案，比所有其他孩子的速度都快。 我们先来做一个“合理假设”： 做 1 次加法用时 1 秒 做 1 次乘法用时 10 秒 做 1 次除法用时 15 秒 学习活动2：累加运算的效率分析 第一种算法：逐个进行累加 1+2+3+…+100 99次加法 每次加法用时1秒 总共需要99秒 第二种算法：根据公式计算 s = （1+n）* n / 2 只需要一次加法（1+100）用时1秒 1次乘法（101×100）用时10秒 1次除法（除以2）用时15秒 总共需要26秒 单从计算步骤和时间上看，第 种算法似乎更高效。 这就是在“合理假设”前提下，高斯比其他同学算得更快的一种解释。 学习活动2：累加运算的效率分析 但是，问题并没有那么简单。 因为做乘法和除法时，通常比做加法需要更长时间。 因此，如果以上假设并不成立，比如，如果做 1 次乘法或 1 次除法都需要 50 秒，那么用第二种算法所需的时间就会变成 1 + 50 + 50 =101 秒 。 从用算法解决问题的角度看，要准确地比较不同算法的效率，往往比我们预想的要难很多。通常需要从数据量、步骤多少、所需时间等方面综合考虑。 学习活动三：感受不同算法的运算效率 学习活动3：感受不同算法的运算效率 解决同一个问题通常可以用不同的算法，选择不同算法并编程实现后，程序一般会在运算速度、计算精度等方面有不同的表现。 下面通过用程序验证上述累加运算的两种算法： “累加 1.py”程序是用算式直接累加与用公式累加的对比。 “累加 2.py”程序是用循环结构实现累加与用公式累加的对比。 学习活动3：感受不同算法的运算效率 在“累加 1.py”程序中，操作步骤如下： 第 1 步：打开配套资源中的“累加 1.py”程序，运行这个程 ... ...
