资源简介

(共10张PPT)
六年级上册 信息科技
算法的评价方法
第9课
你将学习
1.算法评价的方法。
2.多种算法的效率比较。
讨论
哪条路更好呢？
建构
一个问题，可以设计多个算法来解决。
但不同算法的效率是有差异的。
算法有“好”与“坏”之分。
算法评价的方法
正确性、有效性
算法运行效率
时间复杂度
空间复杂度
时间
内存空间
算法的评价方法
采用“按顺序依次查找”的策略，查找数37，一共需比较多少次呢？
1 2 3 …… 50 51 52 …… 99 100
37次
采用“按二分查找”的策略，查找数37，一共需比较多少次呢？
3次
算法的评价方法
试一试：修改程序，增加一个变量ci来统计while语句的执行次数，并显示数值。
1 2 3 …… 50 51 52 …… 99 100
da=137
cai=1
while cai<101:
if cai==da:
print("找到了!")
break
else:
cai=cai+1
if cai>100:
print("找不到！")
ci=0
ci=ci+1
print(“找到了！共用了”,ci,“次。”)
print(“找不到！共用了”,ci,“次。”)
da=137
cai=1
ci=0
while cai<101:
ci=ci+1
if cai==da:
print("找到了!共用了",ci,"次。")
break
else:
cai=cai+1
if cai>100:
print("找不到！共用了",ci,"次。")
算法评价体验
二分查找算法，只需循环3次就找到了！
与顺序查找算法相比，循环少执行34次。运行时间更短！
效率更高！
算法评价体验
想一想：在1~1000范围内查找目标数37，利用二分查找算法，循环执行的次数是多少？
第1次中间值（1001÷2） 500，比较 37<500，范围 1~499
第2次中间值（500÷2） 250，比较 37<250，范围 1~249
第3次中间值（250÷2） 125，比较 37<125，范围 1~124
第4次中间值（125÷2） 62，比较 37<62，范围 1~61
第5次中间值（62÷2） 31，比较 37>31，范围 32~61
第6次中间值（93÷2） 46，比较 37<46，范围 32~45
第7次中间值（77÷2） 38，比较 37<38，范围 32~37
第8次中间值（69÷2） 34，比较 37>34，范围 35~37
第9次中间值（72÷2） 36，比较 36<37，范围 37
练习

展开更多......

收起↑