资源简介

(共33张PPT)
第8单元 第2课
问题规模影响算法执行时间
（黔教版）五年级
下
1
核心素养目标
3
新知讲解
5
拓展延伸
7
板书设计
2
新知导入
4
课堂练习
6
课堂总结
课后作业
8
01
核心素养目标
信息意识
计算思维
数字化学习与创新
信息社会责任
明白根据问题规模优化算法，不仅可以提高技术效率，也有助于节约资源等，体现了在信息化社会中对可持续发展和社会责任的承担。
在实际操作中理解算法的执行时间如何受问题规模变化的影响，进而在设计新的算法时更注重创新和效率提升。
通过学习本课内容，能够帮助学生从问题规模的增长中预测计算复杂度，并尝试优化解决方案。
能够具备良好的信息意识，这样才能更好地理解如何通过优化算法，降低计算资源消耗，从而提高效率。
02
新知导入
我们可以利用不同的猜数范国围多做一些判断。
依据一个猜数范围就判断猜数算法的效率，未必是可靠的。
猜数范围会影响猜测次数，也就是算法步骤的执行次数与问题的规模有关。
02
新知导入
03
新知讲解
一、步骤执行次数与问题规模有关
猜数游戏中，猜测步骤的执行次数会受到要猜数字自身数值的影响，最少1次就猜中，最多甚至需要将所有数字猜一遍。最多猜测次数对衡量算法的好坏具有实际意义，所以我们可以利用最多猜测次数进行算法效率的比较。
猜测步骤的执行次数还会受到猜数范围的影响，随着猜数范围的变化，猜测步骤的最多执行次数会发生怎样的变化呢
03
新知讲解
活动：比较不同猜数范围的猜测次数
选择本单元第1课中的“猜数算法1”猜数，为了使猜数次数最多，每次猜测的数字都是猜数范围的最大值。
1. 当所猜数字范围分别是0~20、0~50、0~100、0~150时，请你分析各需要猜测多少次才能猜中，并填写表8-2-1。
03
新知讲解
表 8-2-1 不同猜测范围的猜中次数记录
游戏序次 第1次 第2次 第3次 第4次
目标数字 20 50 100 150
猜测的范围 0~20 0~50 0~100 0~150
猜中时的猜测次数 5 6 7 8
03
新知讲解
2. 利用“折半查找”程序，通过调整猜数范围参数，验证你的结果是否正确，并填写表8-2-2。
游戏序次 第1次 第2次 第3次 第4次
目标数字 20 50 100 150
猜测的范围 0~20 0~50 0~100 0~150
猜中时的猜测次数 5 6 7 8
是否与我的结果一致 是 是 是 是
表 8-2-2 猜数结果对比
03
新知讲解
3.猜数范围增加后，猜测次数是否也增加了 是否增加了同样的倍数
果猜测的范围增加，猜测次数的增加取决于算法的时间复杂度。
例如，如果算法的时间复杂度是O(log n)，那么范围增加后，猜测次数的增加不是线性的，而是对数级的；如果时间复杂度是O(n)，那么增加的次数会是线性增长。因此，范围的增加不一定会导致猜测次数按同样的倍数增加，具体增加的倍数取决于算法的时间复杂度。
03
新知讲解
“猜数算法 1”采用的是折半查找，折半查找要求线性表中的元素是有序排列的。
当线性表中的元素按照从小到大的顺序排列时，折半查找的具体过程如下:
将被查元素与线性表中间的元素进行比较，有3种可能:
拓展阅读
03
新知讲解
(1)如果表中间的元素等于被查元素，表示查找成功；
(2)如果表中间的元素>被查元素，表示被查元素只能在查找表的前半部分，则在前半部分继续进行折半查找；
(3)如果表中间的元素<被查元素，表示被查元素只能在查找表的后半部分，则在后半部分继续进行折半查找。
拓展阅读
03
新知讲解
随着数据输入规模的增加，猜测步骤的最多执行次数也随之增加，但是和数据输人规模增加的倍数并不一致。
03
新知讲解
二、算法的时间效率可估算
将“猜数算法 1”与“猜数算法 4”进行比较，分析哪个算法的效率高。将每次猜测的数字都设为猜数范围的最大值。
1. 当所猜数字范围分别是0~10、0~100、0~1 000、0~10 000 时，两种算法分别需要多少次才能猜中 填写表8-2-3。
活动：对比不同算法的时间效率
03
新知讲解
表 8-2-3 两种算法的猜中次数记录
游戏序次 第1次 第2次 第3次 第4次
目标数字 10 100 1000 10000
猜测的范围 0~10 0~100 0~1000 0~10000
“猜数算法 1”猜中时的猜测次数 4 7 10 14
“猜数算法 4”猜中时的猜测次数 10 100 1000 10000
03
新知讲解
2.分别运行“折半查找”和“顺序查找”程序，通过调整猜数范围参数，验证你的猜测结果是否正确。
3.根据你的发现，分别为两种算法的猜中次数绘制折线图，你认为哪种算法的效率高
从理论上来说，折半查找（猜数算法1）的效率更高。因为折半查找每次都将查找范围缩小一半，而顺序查找是逐个数字进行尝试。随着猜测范围的增大，折半查找的增长速度远远慢于顺序查找。
03
新知讲解
“猜数算法 4”采用的是顺序查找。顺序查找的基本思想是:从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较，如果某个元素等于被查元素，则查找成功，停止查找;如果将线性表中所有元素都比较完，仍未找到与被查元素相等的元素，则查找失败。
拓展阅读
03
新知讲解
无论基于哪种算法猜数字，随着猜数范围的扩大，猜数步骤的执行次数均会增加。但是随着输人规模的增大，我们发现顺序查找的猜测次数相对较多，效率较低;折半查找的猜测次数相对较少，效率较高。当猜数范围不断扩大时，不同算法的效率差异会越来越明显。也就是，随着问题规模的增加，可以通过算法中某些步骤的执行次数变化趋势比较算法效率的高低。
04
课堂练习
一、选择题
1、如果问题规模增加，时间复杂度为O(n^2)的算法执行时间会：
A. 增加线性倍数 B. 增加平方倍数
C. 增加对数倍数 D. 不变
2、在问题规模不变的情况下，哪种算法执行时间最短？
A. O(n) B. O(n log n)
C. O(n^2) D. O(log n)
B
D
04
课堂练习
3、下列哪种算法的时间复杂度为O(log n)
冒泡排序 B. 二分查找 C. 快速排序 D. 线性查找
二、判断题
1、时间复杂度为O(n log n)的算法比时间复杂度为O(n^2)的算法在大规模问题上更高效。
2、随着问题规模的增加，O(1)时间复杂度的算法执行时间将显著增加。
3、如果一个算法的时间复杂度是O(n log n)，那么随着问题规模n的增加，算法的执行时间增长是对数级的。
B
√
X
X
04
课堂练习
三、操作题
编写一个排序算法并计算其在不同数据规模下的执行时间。可以选择冒泡排序、快速排序等，分析其时间复杂度与实际执行时间的关系。
05
拓展延伸
时间复杂度与空间复杂度
除了时间复杂度，空间复杂度也是影响算法效率的重要因素。
贪心算法：贪心算法通常具有较低的时间复杂度，但可能需要较高的空间复杂度。例如，快速排序通常可以使用O(log n)的空间，但最坏情况下可能需要O(n)的空间。选择合适的贪心策略可以提高时间效率，尽管其空间复杂度可能较高。
05
拓展延伸
时间复杂度与空间复杂度
选择合适的数据结构：选择合适的数据结构可以在提高效率的同时减少空间消耗。例如，在需要频繁插入、删除元素的场景中，使用链表比数组更适合；而对于需要快速查找的场景，哈希表可能比数组更高效。
05
拓展延伸
分治法与动态规划
分治法与动态规划是两种常用的算法设计思想，它们都涉及到将大问题拆解成小问题的策略，但使用的场景和方法略有不同。
分治法：
分治法通过递归将问题分解为多个子问题，直到问题变得足够简单，可以直接求解。然后，通过合并子问题的解来得到最终结果。
典型的应用有归并排序、快速排序、二分查找等。
分治法的一个关键特点是子问题通常是独立的，不会有重叠。
05
拓展延伸
分治法与动态规划
动态规划：
动态规划是通过解决重叠子问题的方式来优化分治法。其关键在于通过保存子问题的解来避免重复计算，从而提高效率。
动态规划的应用通常涉及到最优子结构和重叠子问题。经典问题如最长公共子序列、背包问题、斐波那契数列等。
与分治法不同，动态规划更注重将子问题的解存储在表格中，避免重复计算，从而节省时间，但可能增加空间消耗。
05
拓展延伸
大数据与并行计算
分布式计算框架（如 Hadoop, Spark）：
Hadoop：Hadoop是一个开源的大数据处理框架，采用MapReduce编程模型。它将大规模计算分割成多个任务并在多个节点上并行处理，适合处理海量数据。
Spark：Spark比Hadoop的MapReduce模型更高效，它支持内存中的数据处理，可以比Hadoop更快地处理迭代算法，适合实时数据分析和机器学习等应用。
05
拓展延伸
大数据与并行计算
并行算法（如MapReduce）：
MapReduce：MapReduce是一种编程模型，常用于大规模数据集的处理。它将任务分为两个阶段：Map阶段（数据的分配和局部处理）和Reduce阶段（结果的合并）。这种模型可以在分布式系统中并行处理大量数据。
在进行并行计算时，数据的划分与负载均衡非常关键。MapReduce将任务分解成多个小任务，通过多个计算节点并行处理，从而大大缩短处理时间。
05
拓展延伸
大数据与并行计算
在解决大规模问题时，算法的选择不仅需要考虑时间和空间的复杂度，还要考虑实际的计算资源。例如，分治法和动态规划可以有效地将大问题分解为小问题，提高效率；而在分布式计算框架和并行算法的帮助下，能够进一步解决问题规模带来的时间瓶颈。
06
课堂总结
1
引入新知内容
问题规模影响算法执行时间
2
步骤执行次数与问题规模有关
3
算法的时间效率可估算
4
完成课题练习
5
进行相关知识拓展
1
2
3
4
5
07
板书设计
问题规模影响算法执行时间
1、进行新知引入
2、步骤执行次数与问题规模有关
3、算法的时间效率可估算
4、完成课堂练习
5、进行知识拓展
课后作业。
1、测试不同规模的输入数据对查找算法执行时间的影响。
08
课后作业
1、设计一个程序，测试不同规模的输入数据对查找算法（如线性查找、二分查找）执行时间的影响，并绘制执行时间与输入规模的关系图。
https://www.21cnjy.com/recruitment/home/fine

展开更多......

收起↑