单元四 · 发挥算法的优势
第14课 算法效率比一比
一、学习目标
- 知道解决同一个问题可以有不同的算法，不同的算法具有不同的效率。
- 通过实例比较和算法分析，了解算法执行的关键步骤和执行次数，体会算法存在的效率差异。
二、情境导入
一堆物体摆放如图所示，要统计有多少个，你能想到哪些方法？这些方法有什么不同呢？
三、核心讲解
本课学习路径：
1用不同方法统计物体数量
2累加运算的效率分析
3感受不同算法的运算效率
1．用不同方法统计物体数量
要统计梯形中物体的个数，常用的有两种方法：
- 算法 1：逐个累加，1+2+3+4+5+6+7+8+9+10 = 55。
- 算法 2：平行四边形中物体个数 = 每层个数×层数 = (1+10)×10÷2 = 55；梯形中物体个数 = 平行四边形中物体个数÷2 = 110÷2 = 55。
自然数从 1 到 n 的累加之和：s = (1 + n) × n ÷ 2。例如 n = 10 时，s = (1+10)×10÷2 = 55。
方法对比：算法 1 简单直观、易于理解；算法 2 所用的步数较少，计算起来更快。解决同一个问题时，不同的算法会有不同的步骤，也就可能存在不同的效率。
2．累加运算的效率分析
用计算机比较算法效率，通常有两种方法：一是比较运行时间；二是比较执行步数或占用资源。下面主要从时间上来分析。
想一想：大家听过数学家高斯小时候计算「1+2+3+…+100」的故事吧？
假设做 1 次加法用时 1 秒、1 次乘法用时 10 秒、1 次除法用时 15 秒：
- 第一种算法：约 99 次加法，需要大约 99 秒。
- 第二种算法：1 次加法、1 次乘法、1 次除法，约 1+10+15 = 26 秒。
但如果乘法、除法各需 50 秒，第二种算法就变成 101 秒——问题并没有那么简单！要准确比较算法效率，通常需要从数据量、步骤多少、所需时间等方面综合考虑。
3．感受不同算法的运算效率
下面通过程序验证累加运算的两种算法，体会效率差异：
- 用循环结构实现累加，与用公式 s = n×(n+1)÷2 一次算出结果对比。
- 分别用较大的 n（如 5000、10000）运行，观察两种方法的速度差异。
- 尝试用更多更大的数反复实验，依据结果总结算法效率。
流程图：循环累加求和
流程图：公式一次求和
本课对比算法效率，语法与积木均已讲过。请对照下方程序观察循环次数。
弄清以上要点后，再进入下方 Python Online，对比循环求和与公式求和的效率。
四、动手体验 · Python 3 Online 编程
本课含 4 个程序，请在下拉中切换后分别「载入」运行。
正在载入 Python 3 Online
正在载入编程环境…
五、课堂总结
- 解决同一个问题时，不同的算法会有不同的步骤，也就存在不同的效率。
- 用计算机解决问题时，通常会从执行步骤、执行时间、内存占用等方面比较算法的效率。
- 有些人计算起来较困难的问题，可以尝试通过算法利用计算机来解决，充分发挥计算机的计算速度和存储能力优势。
六、拓展提升
- 计算圆周率的效率比较。圆周率作为数学中的重要常数，其更多位数的精确值求解一直是数学家们所追求的。我国南北朝时期的祖冲之推算出 π 的值在 3.1415926 和 3.1415927 之间。可在下方动手体验中切换「循环求和」「公式求和」，以及拓展程序「圆周率循环逼近」「圆周率公式估算」，对比不同算法与写法的效率差异。
测评
选出后点「检查」。答错会显示简短说明。
关于算法效率，下列说法正确的是？
高斯快速计算 1+2+…+100 的故事说明了什么？
用计算机比较算法效率时，通常可以从哪些方面入手？
本节小结
同一问题可有多种算法，效率各异；比较时要综合数据量、步骤与时间。公式求和往往比循环累加更高效。