資源簡介

(共10張PPT)
六年級上冊 信息科技
算法的評價方法
第9課
你將學習
1.算法評價的方法。
2.多種算法的效率比較。
討論
哪條路更好呢？
建構
一個問題，可以設計多個算法來解決。
但不同算法的效率是有差異的。
算法有“好”與“壞”之分。
算法評價的方法
正確性、有效性
算法運行效率
時間復雜度
空間復雜度
時間
內存空間
算法的評價方法
采用“按順序依次查找”的策略，查找數37，一共需比較多少次呢？
1 2 3 …… 50 51 52 …… 99 100
37次
采用“按二分查找”的策略，查找數37，一共需比較多少次呢？
3次
算法的評價方法
試一試：修改程序，增加一個變量ci來統(tǒng)計while語句的執(zhí)行次數，并顯示數值。
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,"次。")
算法評價體驗
二分查找算法，只需循環(huán)3次就找到了！
與順序查找算法相比，循環(huán)少執(zhí)行34次。運行時間更短！
效率更高！
算法評價體驗
想一想：在1~1000范圍內查找目標數37，利用二分查找算法，循環(huán)執(zhí)行的次數是多少？
第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
練習

展開更多......

收起↑