资源简介

第14 课算法效率比一比
一、教学目标
1.知道解决同一个问题可以有不同的算法，不同的算法具有不同的效率。
2.通过实例比较和算法分析，了解算法执行的关键步骤和执行次数，体会算法存在的效率差异。
二、教学重点与难点
教学重点
1.理解不同算法的效率差异。
2.分析算法的关键步骤和执行次数。
教学难点
1.准确评估不同算法的效率。
2.选择合适的算法解决问题。
三、教学准备
1.多媒体课件，包含不同算法的示例、效率比较等内容。
2.纸、笔，供学生进行分析和计算。
四、教学过程
（一）导入新课
师：同学们，在我们解决问题的时候，往往可以有多种方法。就像我们去学校，可以走路、骑自行车、坐公交车等。在计算机编程中，解决同一个问题也可以有不同的算法。那么，不同的算法会有什么不同呢？今天我们就来一起比较一下算法的效率。
（二）新课讲解
1.引出不同算法解决同一个问题的概念
师：我们以一个简单的问题为例，计算从1到100的和。大家想想，可以用哪些方法来解决这个问题呢？
生：可以一个一个地加起来。
生：还可以用公式（首项+末项）×项数÷2。
师：非常好！这就是两种不同的算法来解决同一个问题。我们先来看看第一种算法，一个一个地加起来。
2.分析第一种算法：逐个相加
（1）描述算法过程
师：这种算法的过程很简单，就是从1开始，依次加上2、3、4……一直加到100。
我们可以用Python语言来实现这个算法：
total=0 for I in range(1,101): total+=i print(total)
（2）分析关键步骤和执行次数
师：在这个算法中，关键步骤就是每次的加法运算。执行次数是多少呢？我们可以分析一下。
因为要从1加到100，一共要进行100次加法运算。所以这个算法的执行次数是100次。
3.分析第二种算法：使用公式
（1）描述算法过程
师：第二种算法是使用公式（首项+末项）×项数÷2。在这个问题中，首项是1，末项是100，项数是100。
我们可以用Python语言来实现这个算法：
sum=(1+100)*100//2 print(sum)
（2）分析关键步骤和执行次数
师：在这个算法中，关键步骤就是一次加法、一次乘法和一次除法运算。执行次数只有这三次。
4.比较两种算法的效率
（1）从执行次数角度比较
师：我们可以明显看出，第一种算法需要进行100次加法运算，而第二种算法只需要进行一次加法、一次乘法和一次除法运算。从执行次数上来说，第二种算法远远少于第一种算法。
（2）从实际运行时间角度比较
师：我们可以在计算机上运行这两种算法，看看它们实际的运行时间。虽然这个时间可能会因为计算机的性能不同而有所差异，但是一般来说，第二种算法的运行时间会比第一种算法短很多。
5.拓展不同算法解决其他问题的例子
（1）排序问题
师：比如我们要对一个列表中的数字进行排序。可以使用冒泡排序算法，也可以使用快速排序算法。
冒泡排序算法的基本思想是：每次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。这样一遍一遍地比较和交换，直到整个列表都有序为止。
快速排序算法的基本思想是：先从列表中选取一个元素作为基准值，然后把列表分成两部分，一部分比基准值小，一部分比基准值大。然后对这两部分分别进行快速排序，直到整个列表都有序为止。
（2）查找问题
师：再比如我们要在一个列表中查找一个特定的元素。可以使用顺序查找算法，也可以使用二分查找算法。
顺序查找算法就是从列表的第一个元素开始，依次比较每个元素，直到找到目标元素或者遍历完整个列表。
二分查找算法是针对有序列表的，每次取中间元素进行比较，如果目标元素等于中间元素，就找到了；如果目标元素小于中间元素，就在左边的子列表中继续查找；如果目标元素大于中间元素，就在右边的子列表中继续查找。
（三）巩固练习
1.基础练习
（1）让学生用两种不同的算法计算从1到50的和，并比较它们的执行次数和运行时间。
第一种算法：逐个相加。
total=0 for I in range(1,51): total+=i print(total)
第二种算法：使用公式。
sum=(1+50)*50//2 print(sum)
学生通过分析可以得出，第一种算法需要进行50次加法运算，执行次数较多；第二种算法只需要进行一次加法、一次乘法和一次除法运算，执行次数较少。在实际运行时间上，第二种算法也会比第一种算法短。
（2）给出一个包含10个数字的列表，让学生分别用顺序查找算法和二分查找算法查找一个特定的数字，并记录它们的执行次数和运行时间。
顺序查找算法：
list=[2,5,8,11,14,17,20,23,26,29] target=17 found=False for num in list: if num==target: found=True break if found: print("找到了目标数字。") else: print("没有找到目标数字。")
二分查找算法：
list=[2,5,8,11,14,17,20,23,26,29] target=17 left=0 right=len(list)-1 while left<=right: mid=(left+right)//2 if list[mid]==target: print("找到了目标数字。") break elif list[mid]right: print("没有找到目标数字。")
学生通过实践可以发现，顺序查找算法需要依次比较每个数字，最坏情况下需要比较10次；而二分查找算法每次都将查找范围缩小一半，最多需要比较4次。在运行时间上，二分查找算法也会更快。
2.拓展练习
（1）让学生思考如何改进冒泡排序算法，使其效率更高。
学生可以提出一些改进的方法，比如在某次遍历中如果没有发生交换，就说明列表已经有序，可以提前结束排序。或者可以记录最后一次交换的位置，下次遍历只需要到这个位置即可。
（2）给出一个更大的列表，让学生分别用不同的排序算法（如选择排序、插入排序、归并排序等）对其进行排序，并比较它们的效率。
选择排序算法：
list=[12,5,18,3,21,8,15,6,24,10] for I in range(len(list)): min_index=i for j in range(i+1,len(list)): if list[j]插入排序算法：
Def merge_sort(list): If len(list)<=1: Return list mid=len(list)//2 left=merge_sort(list[:mid]) right=merge_sort(list[mid:]) return merge(left,right) def merge(left,right): result=[] i=j=0 while i学生通过对不同排序算法的实践和比较，可以发现不同算法的效率差异，并且在实际应用中可以根据数据规模和特点选择合适的排序算法。
3.综合练习
（1）将学生分成小组，每个小组选择一个问题，设计多种不同的算法来解决这个问题，并比较它们的效率。然后，每个小组推选一位代表向全班同学展示自己小组的问题和解决方案，并进行讲解。
例如，一个小组选择的问题是计算两个矩阵的乘积。小组可以设计不同的算法，如直接按照矩阵乘法的定义进行计算，或者使用分治法等。然后比较这些算法的执行次数、运行时间等效率指标。
（2）让学生讨论在实际编程中，如何选择合适的算法来解决问题。
学生可以从问题的特点、数据规模、时间和空间复杂度等方面进行讨论，得出在选择算法时需要综合考虑各种因素，以达到最优的解决方案。
（四）课堂小结
1.回顾本节课的主要内容
师：同学们，今天我们学习了算法效率的比较。我们知道了解决同一个问题可以有不同的算法，不同的算法具有不同的效率。我们通过实例比较和算法分析，了解了算法执行的关键步骤和执行次数，体会了算法存在的效率差异。
2.强调重点和难点
师：本节课的重点是理解不同算法的效率差异，分析算法的关键步骤和执行次数。难点是准确评估不同算法的效率，选择合适的算法解决问题。希望同学们在课后能够多做一些练习，加深对这些知识的理解和掌握。
（五）作业布置
1.完成课后练习中的相关题目。
2.自己选择一个问题，设计多种不同的算法来解决这个问题，并比较它们的效率。
五、板书设计
1.不同算法解决同一问题
2.算法效率比较方法
3.关键步骤与执行次数
4.实例分析（求和、排序、查找等）
六、课后反思
在本节课的教学中，通过具体的例子引出不同算法解决同一个问题的概念，让学生直观地感受到算法效率的差异。在新课讲解环节，详细地分析了不同算法的过程、关键步骤和执行次数，使学生深入理解算法效率的影响因素。在巩固练习环节，设计了多种形式的练习，包括基础练习、拓展练习和综合练习，让学生在实践中比较不同算法的效率，提高了学生的分析问题和解决问题的能力。
然而，在教学过程中也发现了一些问题。部分学生在理解复杂算法的过程和效率分析时还有一些困难，需要在今后的教学中进一步加强引导。另外，在小组合作练习中，有些小组的讨论不够深入，需要在今后的教学中加强小组合作的指导，提高学生的合作能力和思维深度。
总的来说，本节课的教学目标基本达成，学生对算法效率的比较有了初步的认识和理解。在今后的教学中，要继续关注学生的学习情况，及时调整教学方法，提高教学效果。

展开更多......

收起↑