资源简介

(共25张PPT)
第9课 算法的评价方法
年 级：六年级
学 科：小学信息科技（浙教版）
1 2 … 36 37 38 … 98 99 100
查找成功
算法一：顺序查找
目标数：37
算法二：二分查找
1 2 … 49 50 51 … 98 99 100
1 2 … 24 25 26 … 48 49
26 27 … 36 37 38 … 48 49
中间数
初值
终值
中间数
初值
终值
中间数
初值
终值
查找成功
同桌互助，运行“猜数字”游戏顺序查找与二分查找的算法模型，比一比：谁猜的次数更少？
目标数：37
猜数字游戏
·如何评价顺序查找与二分查找算法的“好”与“差”？
算法评价方法
·“好”的算法有哪些评价标准？
·哪些因素会影响算法运行效率？
·估算算法运行时间的度量标准是什么？
——组内讨论，生成问题
算法评价方法
有效性
运行效率
算法运行所消耗的时间较短
正确性
数据规模
数据的值
度量标准
算法中循环语句的执行次数
“好”算法标准
——梳理概念，提出猜想
按要求填写学习任务单中的表1：
1.用顺序查找算法在1~100内查找数37，估算循环语句的执行次数。
2.在顺序查找程序中增加变量ci来统计while语句的执行次数，运行算法，记录结果。
3.重复上述2个步骤，独立完成二分查找算法。
实验一：计算循环语句的执行次数
表1:计算循环语句的执行次数
目标数 循环执行次数 顺序查找 二分查找 估算结果 程序验证结果 估算结果 程序验证结果
37
顺序查找算法估算
37次
估算结果：37
1 2 … 36 37 38 … 98 99 100
1 2 … 36 37 38 … 98 99 100
……
查找成功
验证：顺序查找算法计数
二分查找算法估算
循环轮次 cz（初值） zz（终值） cai（中间值） 查找结果
1 1 100 50 未找到
2 1 49 25 未找到
3 26 49 37 查找成功
中间数 = (初值+终值)//2
算法二：二分查找
1 2 … 49 50 51 … 98 99 100
1 2 … 24 25 26 … 48 49
26 27 … 36 37 38 … 48 49
中间数
初值
终值
中间数
初值
终值
中间数
初值
终值
查找成功
目标数：37
大问题
子问题
子问题
3次
验证：二分查找算法计数
录屏2
两人小组合作，运行相应程序，完成算法运行所消耗时间的对比实验。在学习任务单中的表2和表3中记录结果，并填写实验结论。
实验二：算法效率的影响因素
数据规模 目标数 算法运行消耗时间（秒） 我的发现
生1：顺序查找 生2：二分查找 1~1000 37
1~10000 1~100000 表2：同一算法在不同数据规模下的效率影响
数据规模 目标数 算法运行消耗时间（秒） 我的发现
生1：顺序查找 生2：二分查找 1~100000 137
1370 13700 实验结论：从上面两个实验发现，一个算法的 和 影响着算法的效率。算法效率会随着要素的改变而改变，数据规模越大，可能会使算法中的循环语句执行次数越多，算法效率越 。（填写“高”或 “低”）
表3：同一算法在不同数据值下的效率影响
·待求问题的规模
·循环语句执行次数

计时程序实现原理
算法伪代码：
run_fun() #表示待测程序代码
t1 = 开始时间
t2 = 结束时间
t = t2 - t1 #计算出两个时间点之间的差异
print(t) #显示运行时间
顺序查找算法计时程序
数据规模 目标数 算法运行消耗时间（秒） 我的发现
生1：顺序查找 生2：二分查找 1~100000 137
1370 13700 数据规模 目标数 算法运行消耗时间（秒） 我的发现
生1：顺序查找 生2：二分查找 1~1000 37
1~10000 1~100000 顺序查找算法效率的影响因素
表2：同一算法在不同数据规模下的效率影响
表3：同一算法在不同数据值下的效率影响
同一算法在不同数据规模下对运行效率影响很小
0.00001030
0.00000918
0.00000934
同一算法在不同数据值下对运行效率影响很大
0.00003216
0.00032288
0.00303226
数据规模 目标数 算法运行消耗时间（秒） 我的发现
生1：顺序查找 生2：二分查找 1~100000 137
1370 13700 数据规模 目标数 算法运行消耗时间（秒） 我的发现
生1：顺序查找 生2：二分查找 1~1000 37
1~10000 1~100000 二分查找算法效率的影响因素
同一算法在不同数据规模下对运行效率影响不大
0.00000952
表2：同一算法在不同数据规模下的效率影响
表3：同一算法在不同数据值下的效率影响
0.00002276
0.00001288
同一算法在不同数据值下对运行效率影响不大
0.00002494
0.00001866
0.00002686
和 影响着算法的效率。算法效率会随着要素的改变而改变，数据规模越大，可能会使算法中的循环语句执行次数越多，算法效率越 。（填写“高”或 “低”）
从上面两个实验发现，一个算法的 。
数据规模
数据的值
低
实验结论
实验二：算法效率的影响因素
表4：不同算法在相同输入数据下的效率对比
对比轮次 目标数 算法 循环执行次数 算法运行消耗时间（秒） 效率评估（高或低）
第一次对比 1 顺序
二分
第二次对比 50000 顺序
二分
第三次对比 100000 顺序
二分
自主探究：运行程序，对比不同算法在相同输入数据下的效率。在学习任务单中表4中记录结果（其中，数据规模：1~100000）；分析结果后填写结论。
实验变量
实验不变量
实验三：不同算法运行效率对比
不同算法之间的效率
如何探究？
16
1
100000
17
1
50000
0.00000260
0.00001414
高
低
0.01740532
0.00000334
低
高
0.03301638
0.00001968
低
高
实验三：不同算法运行效率对比
实验结论：解决同一个问题的不同算法在相同的输入数据（数据规模和数据的值）情形下，循环执行次数可能相差很 ，那么算法执行时间相差就很 。（填写“大”或 “小”）
大
大
表4：不同算法在相同输入数据下的效率对比
对比轮次 目标数 算法 循环执行次数 算法运行消耗时间（秒） 效率评估（高或低）
第一次对比 1 顺序
二分
第二次对比 50000 顺序
二分
第三次对比 100000 顺序
二分
自主探究：运行程序，对比不同算法在相同输入数据下的效率。在学习任务单中表4中记录结果（其中，数据规模：1~100000）；分析结果后填写结论。
16
1
100000
17
1
50000
0.00000260
0.00001414
高
低
0.01740532
0.00000334
低
高
0.03301638
0.00001968
低
高
数据规模 目标数 算法运行平均时间（秒） 高效
算法
顺序查找 二分查找 1~100 1-100
1~500 1-500
1~1000 1-1000
演示实验：综合效率对比
0.00001417
0.00000639
二分查找
0.00006805
0.00000925
二分查找
0.00013010
0.00000891
二分查找
在相同有序数据规模内，分别采用顺序查找和二分查找算法，遍历数据规模中的所有目标数，取平均值对算法进行综合评价。思考：猜数字游戏中哪个算法更具价值？
实验结论： 算法效率更高，在猜数字游戏场景应用中更具价值。
二分查找
拓展实验：综合效率对比
一个算法具有价值，也存在着一定的局限性。
“好”的算法
高效率 低存储
自我评价
《第9课 算法的评价方法》自我评价
https://ks.wjx.top/vm/YFJApwF.aspx#
网址
作业
在1~100范围内，分别采用顺序查找和二分查找算法查找目标数1、50和100，估算循环的执行次数，逐次对算法进行效率评估。
次数 目标数 查找算法 循环执行次数 效率评估
第一次 1 顺序
二分
第二次 50 顺序
二分
第三次 100 顺序
二分
《第9课 算法的评价方法》小结
评价方法：
估算
计数
计时
运行效率
效率对比
数据规模
数据的值
影响
影响
价值定位
谢谢观看！
Thanks!
https://www.21cnjy.com/recruitment/home/fine

展开更多......

收起↑