資源簡介

第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.實例分析（求和、排序、查找等）
六、課后反思
在本節課的教學中，通過具體的例子引出不同算法解決同一個問題的概念，讓學生直觀地感受到算法效率的差異。在新課講解環節，詳細地分析了不同算法的過程、關鍵步驟和執行次數，使學生深入理解算法效率的影響因素。在鞏固練習環節，設計了多種形式的練習，包括基礎練習、拓展練習和綜合練習，讓學生在實踐中比較不同算法的效率，提高了學生的分析問題和解決問題的能力。
然而，在教學過程中也發現了一些問題。部分學生在理解復雜算法的過程和效率分析時還有一些困難，需要在今后的教學中進一步加強引導。另外，在小組合作練習中，有些小組的討論不夠深入，需要在今后的教學中加強小組合作的指導，提高學生的合作能力和思維深度。
總的來說，本節課的教學目標基本達成，學生對算法效率的比較有了初步的認識和理解。在今后的教學中，要繼續關注學生的學習情況，及時調整教學方法，提高教學效果。

展開更多......

收起↑