第8单元第2课《问题规模影响算法执行时间》【黔教版】《信息科技》五年级下册.pptxVIP

第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次目标数字2050100150猜测的范围0~200~500~1000~150猜中时的猜测次数5678

03新知讲解2.利用“折半查找”程序，通过调整猜数范围参数，验证你的结果是否正确，并填写表8-2-2。游戏序次第1次第2次第3次第4次目标数字2050100150猜测的范围0~200~500~1000~150猜中时的猜测次数5678是否与我的结果一致是是是是表8-2-2猜数结果对比

03新知讲解3.猜数范围增加后，猜测次数是否也增加了?是否增加了同样的倍数?果猜测的范围增加，猜测次数的增加取决于算法的时间复杂度。例如，如果算法的时间复杂度是O(logn)，那么范围增加后，猜测次数的增加不是线性的，而是对数级的；如果时间复杂度是O(n)，那么增加的次数会是线性增长。因此，范围的增加不一定会导致猜测次数按同样的倍数增加，具体增加的倍数取决于算法的时间复杂度。

03新知讲解“猜数算法1”采用的是折半查找，折半查找要求线性表中的元素是有序排列的。当线性表中的元素按照从小到大的顺序排列时，折半查找的具体过程如下:将被查元素与线性表中间的元素进行比较，有3种可能:拓展阅读

03新知讲解(1)如果表中间的元素等于被查元素，表示查找成功；(2)如果表中间的元素被查元素，表示被查元素只能在查找表的前半部分，则在前半部分继续进行折半查找；(3)如果表中间的元素被查元素，表示被查元素只能在查找表的后半部分，则在后半部分继续进行折半查找。拓展阅读

03新知讲解随着数据输入规模的增加，猜测步骤的最多执行次数也随之增加，但是和数据输人规模增加的倍数并不一致。

03新知讲解二、算法的时间效率可估算将“猜数算法1”与“猜数算法4”进行比较，分析哪个算法的效率高。将每次猜测的数字都设为猜数范围的最大值。1.当所猜数字范围分别是0~10、0~100、0~1000、0~10000时，两种算法分别需要多少次才能猜中?填写表8-2-3。活动：对比不同算法的时间效率

03新知讲解表8-2-3两种算法的猜中次数记录游戏序次第1次第2次第3次第4次目标数字10100100010000猜测的范围0~100~1000~10000~10000“猜数算法1”猜中时的猜测次数471014“猜数算法4”猜中时的猜测次数10100100010000

03新知讲解2.分别运行“折半查找”和“顺序查找”程序，通过调整猜数范围参数，验证你的猜测结果是否正确。3.根据你的发现，分别为两种算法的猜中次数绘制折线图，你认为哪种算法的效率高?从理论上来说，折半查找（猜数算法1）的效率更高。因为折半查找每次都将查找范围缩小一半，而顺序查找是逐个数字进行尝试。随着猜测范围的增大，折半查找的增长速度远远慢于顺序查找。

03新知讲解“猜数算法4”采用的是顺序查找。顺序查找的基本思想是:从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较，如果某个元素等于被查元素，则查找成功，停止查找;如果将线性表