資源簡介

(共33張PPT)
第8單元 第2課
問題規模影響算法執行時間
（黔教版）五年級
下
1
核心素養目標
3
新知講解
5
拓展延伸
7
板書設計
2
新知導入
4
課堂練習
6
課堂總結
課后作業
8
01
核心素養目標
信息意識
計算思維
數字化學習與創新
信息社會責任
明白根據問題規模優化算法，不僅可以提高技術效率，也有助于節約資源等，體現了在信息化社會中對可持續發展和社會責任的承擔。
在實際操作中理解算法的執行時間如何受問題規模變化的影響，進而在設計新的算法時更注重創新和效率提升。
通過學習本課內容，能夠幫助學生從問題規模的增長中預測計算復雜度，并嘗試優化解決方案。
能夠具備良好的信息意識，這樣才能更好地理解如何通過優化算法，降低計算資源消耗，從而提高效率。
02
新知導入
我們可以利用不同的猜數范國圍多做一些判斷。
依據一個猜數范圍就判斷猜數算法的效率，未必是可靠的。
猜數范圍會影響猜測次數，也就是算法步驟的執行次數與問題的規模有關。
02
新知導入
03
新知講解
一、步驟執行次數與問題規模有關
猜數游戲中，猜測步驟的執行次數會受到要猜數字自身數值的影響，最少1次就猜中，最多甚至需要將所有數字猜一遍。最多猜測次數對衡量算法的好壞具有實際意義，所以我們可以利用最多猜測次數進行算法效率的比較。
猜測步驟的執行次數還會受到猜數范圍的影響，隨著猜數范圍的變化，猜測步驟的最多執行次數會發生怎樣的變化呢
03
新知講解
活動：比較不同猜數范圍的猜測次數
選擇本單元第1課中的“猜數算法1”猜數，為了使猜數次數最多，每次猜測的數字都是猜數范圍的最大值。
1. 當所猜數字范圍分別是0~20、0~50、0~100、0~150時，請你分析各需要猜測多少次才能猜中，并填寫表8-2-1。
03
新知講解
表 8-2-1 不同猜測范圍的猜中次數記錄
游戲序次 第1次 第2次 第3次 第4次
目標數字 20 50 100 150
猜測的范圍 0~20 0~50 0~100 0~150
猜中時的猜測次數 5 6 7 8
03
新知講解
2. 利用“折半查找”程序，通過調整猜數范圍參數，驗證你的結果是否正確，并填寫表8-2-2。
游戲序次 第1次 第2次 第3次 第4次
目標數字 20 50 100 150
猜測的范圍 0~20 0~50 0~100 0~150
猜中時的猜測次數 5 6 7 8
是否與我的結果一致 是 是 是 是
表 8-2-2 猜數結果對比
03
新知講解
3.猜數范圍增加后，猜測次數是否也增加了 是否增加了同樣的倍數
果猜測的范圍增加，猜測次數的增加取決于算法的時間復雜度。
例如，如果算法的時間復雜度是O(log n)，那么范圍增加后，猜測次數的增加不是線性的，而是對數級的；如果時間復雜度是O(n)，那么增加的次數會是線性增長。因此，范圍的增加不一定會導致猜測次數按同樣的倍數增加，具體增加的倍數取決于算法的時間復雜度。
03
新知講解
“猜數算法 1”采用的是折半查找，折半查找要求線性表中的元素是有序排列的。
當線性表中的元素按照從小到大的順序排列時，折半查找的具體過程如下:
將被查元素與線性表中間的元素進行比較，有3種可能:
拓展閱讀
03
新知講解
(1)如果表中間的元素等于被查元素，表示查找成功；
(2)如果表中間的元素>被查元素，表示被查元素只能在查找表的前半部分，則在前半部分繼續進行折半查找；
(3)如果表中間的元素<被查元素，表示被查元素只能在查找表的后半部分，則在后半部分繼續進行折半查找。
拓展閱讀
03
新知講解
隨著數據輸入規模的增加，猜測步驟的最多執行次數也隨之增加，但是和數據輸人規模增加的倍數并不一致。
03
新知講解
二、算法的時間效率可估算
將“猜數算法 1”與“猜數算法 4”進行比較，分析哪個算法的效率高。將每次猜測的數字都設為猜數范圍的最大值。
1. 當所猜數字范圍分別是0~10、0~100、0~1 000、0~10 000 時，兩種算法分別需要多少次才能猜中 填寫表8-2-3。
活動：對比不同算法的時間效率
03
新知講解
表 8-2-3 兩種算法的猜中次數記錄
游戲序次 第1次 第2次 第3次 第4次
目標數字 10 100 1000 10000
猜測的范圍 0~10 0~100 0~1000 0~10000
“猜數算法 1”猜中時的猜測次數 4 7 10 14
“猜數算法 4”猜中時的猜測次數 10 100 1000 10000
03
新知講解
2.分別運行“折半查找”和“順序查找”程序，通過調整猜數范圍參數，驗證你的猜測結果是否正確。
3.根據你的發現，分別為兩種算法的猜中次數繪制折線圖，你認為哪種算法的效率高
從理論上來說，折半查找（猜數算法1）的效率更高。因為折半查找每次都將查找范圍縮小一半，而順序查找是逐個數字進行嘗試。隨著猜測范圍的增大，折半查找的增長速度遠遠慢于順序查找。
03
新知講解
“猜數算法 4”采用的是順序查找。順序查找的基本思想是:從線性表的第一個元素開始，逐個將線性表中的元素與被查元素進行比較，如果某個元素等于被查元素，則查找成功，停止查找;如果將線性表中所有元素都比較完，仍未找到與被查元素相等的元素，則查找失敗。
拓展閱讀
03
新知講解
無論基于哪種算法猜數字，隨著猜數范圍的擴大，猜數步驟的執行次數均會增加。但是隨著輸人規模的增大，我們發現順序查找的猜測次數相對較多，效率較低;折半查找的猜測次數相對較少，效率較高。當猜數范圍不斷擴大時，不同算法的效率差異會越來越明顯。也就是，隨著問題規模的增加，可以通過算法中某些步驟的執行次數變化趨勢比較算法效率的高低。
04
課堂練習
一、選擇題
1、如果問題規模增加，時間復雜度為O(n^2)的算法執行時間會：
A. 增加線性倍數 B. 增加平方倍數
C. 增加對數倍數 D. 不變
2、在問題規模不變的情況下，哪種算法執行時間最短？
A. O(n) B. O(n log n)
C. O(n^2) D. O(log n)
B
D
04
課堂練習
3、下列哪種算法的時間復雜度為O(log n)
冒泡排序 B. 二分查找 C. 快速排序 D. 線性查找
二、判斷題
1、時間復雜度為O(n log n)的算法比時間復雜度為O(n^2)的算法在大規模問題上更高效。
2、隨著問題規模的增加，O(1)時間復雜度的算法執行時間將顯著增加。
3、如果一個算法的時間復雜度是O(n log n)，那么隨著問題規模n的增加，算法的執行時間增長是對數級的。
B
√
X
X
04
課堂練習
三、操作題
編寫一個排序算法并計算其在不同數據規模下的執行時間。可以選擇冒泡排序、快速排序等，分析其時間復雜度與實際執行時間的關系。
05
拓展延伸
時間復雜度與空間復雜度
除了時間復雜度，空間復雜度也是影響算法效率的重要因素。
貪心算法：貪心算法通常具有較低的時間復雜度，但可能需要較高的空間復雜度。例如，快速排序通常可以使用O(log n)的空間，但最壞情況下可能需要O(n)的空間。選擇合適的貪心策略可以提高時間效率，盡管其空間復雜度可能較高。
05
拓展延伸
時間復雜度與空間復雜度
選擇合適的數據結構：選擇合適的數據結構可以在提高效率的同時減少空間消耗。例如，在需要頻繁插入、刪除元素的場景中，使用鏈表比數組更適合；而對于需要快速查找的場景，哈希表可能比數組更高效。
05
拓展延伸
分治法與動態規劃
分治法與動態規劃是兩種常用的算法設計思想，它們都涉及到將大問題拆解成小問題的策略，但使用的場景和方法略有不同。
分治法：
分治法通過遞歸將問題分解為多個子問題，直到問題變得足夠簡單，可以直接求解。然后，通過合并子問題的解來得到最終結果。
典型的應用有歸并排序、快速排序、二分查找等。
分治法的一個關鍵特點是子問題通常是獨立的，不會有重疊。
05
拓展延伸
分治法與動態規劃
動態規劃：
動態規劃是通過解決重疊子問題的方式來優化分治法。其關鍵在于通過保存子問題的解來避免重復計算，從而提高效率。
動態規劃的應用通常涉及到最優子結構和重疊子問題。經典問題如最長公共子序列、背包問題、斐波那契數列等。
與分治法不同，動態規劃更注重將子問題的解存儲在表格中，避免重復計算，從而節省時間，但可能增加空間消耗。
05
拓展延伸
大數據與并行計算
分布式計算框架（如 Hadoop, Spark）：
Hadoop：Hadoop是一個開源的大數據處理框架，采用MapReduce編程模型。它將大規模計算分割成多個任務并在多個節點上并行處理，適合處理海量數據。
Spark：Spark比Hadoop的MapReduce模型更高效，它支持內存中的數據處理，可以比Hadoop更快地處理迭代算法，適合實時數據分析和機器學習等應用。
05
拓展延伸
大數據與并行計算
并行算法（如MapReduce）：
MapReduce：MapReduce是一種編程模型，常用于大規模數據集的處理。它將任務分為兩個階段：Map階段（數據的分配和局部處理）和Reduce階段（結果的合并）。這種模型可以在分布式系統中并行處理大量數據。
在進行并行計算時，數據的劃分與負載均衡非常關鍵。MapReduce將任務分解成多個小任務，通過多個計算節點并行處理，從而大大縮短處理時間。
05
拓展延伸
大數據與并行計算
在解決大規模問題時，算法的選擇不僅需要考慮時間和空間的復雜度，還要考慮實際的計算資源。例如，分治法和動態規劃可以有效地將大問題分解為小問題，提高效率；而在分布式計算框架和并行算法的幫助下，能夠進一步解決問題規模帶來的時間瓶頸。
06
課堂總結
1
引入新知內容
問題規模影響算法執行時間
2
步驟執行次數與問題規模有關
3
算法的時間效率可估算
4
完成課題練習
5
進行相關知識拓展
1
2
3
4
5
07
板書設計
問題規模影響算法執行時間
1、進行新知引入
2、步驟執行次數與問題規模有關
3、算法的時間效率可估算
4、完成課堂練習
5、進行知識拓展
課后作業。
1、測試不同規模的輸入數據對查找算法執行時間的影響。
08
課后作業
1、設計一個程序，測試不同規模的輸入數據對查找算法（如線性查找、二分查找）執行時間的影響，并繪制執行時間與輸入規模的關系圖。
https://www.21cnjy.com/recruitment/home/fine

展開更多......

收起↑