資源簡(jiǎn)介

教學(xué)設(shè)計(jì)
課程基本信息
課題 5.1 數(shù)據(jù)結(jié)構(gòu)與算法效率
教學(xué)目標(biāo)
1. 啟發(fā)學(xué)生認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系。 2. 引導(dǎo)學(xué)生進(jìn)行時(shí)間復(fù)雜度與空間復(fù)雜度的計(jì)算。 3. 通過實(shí)例的形式讓學(xué)生進(jìn)行空間復(fù)雜度的計(jì)算。
4. 知道空間復(fù)雜度。
5. 能理解數(shù)組與鏈表在操作中算法效率的異同。
6. 引導(dǎo)學(xué)生逐步自覺將算法的效率應(yīng)用在算法程序設(shè)計(jì)中，根據(jù)問題選擇合適的數(shù)據(jù)結(jié)構(gòu)，提高算法效率。 指向的核心素養(yǎng) ●信息意識(shí)：學(xué)生能夠結(jié)合實(shí)例，自覺、主動(dòng)地有意識(shí)地選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)表達(dá)信息。 ●計(jì)算思維：學(xué)生能夠結(jié)合實(shí)例，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)。 ●數(shù)字化學(xué)習(xí)與創(chuàng)新：培養(yǎng)學(xué)生自主或協(xié)作探究；能夠評(píng)估常見的數(shù)字化資源與工具對(duì)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的價(jià)值，根據(jù)需要合理選擇。 ●信息社會(huì)責(zé)任：自覺遵守相應(yīng)的倫理道德和法律法規(guī)。
教學(xué)內(nèi)容
教學(xué)重點(diǎn)： 1.時(shí)間復(fù)雜度的計(jì)算。
2.選擇合適的數(shù)據(jù)結(jié)構(gòu)，提高算法效率。
教學(xué)難點(diǎn)： 提高算法效率。
教學(xué)過程
一、認(rèn)識(shí)本節(jié)課的任務(wù)，自學(xué)教材內(nèi)容。 二、情境導(dǎo)入：Google實(shí)驗(yàn) 聯(lián)網(wǎng)上的檢索技術(shù)，它能提高人們獲取搜集信息的速度，為人們提供更好的網(wǎng)絡(luò)使用環(huán)境，Google做過一個(gè)試驗(yàn)，顯示10條搜索結(jié)果的頁面載入需要0.4秒，顯示30條搜索結(jié)果的頁面載入需要0.9秒，結(jié)果后者使得Google總的流量和收入減少了20%。Google地圖上線的時(shí)候，首頁大小有100KB，后來下降到70~80KB。結(jié)果，流量在第一個(gè)星期上升了10%，接下來的3個(gè)星期又再上升了25%。 Amazon（亞馬遜公司）的統(tǒng)計(jì)也顯示了相近的結(jié)果，首頁打開時(shí)間每增加100毫秒，網(wǎng)站銷售量會(huì)減少1%。 三、算法效率的重要性：
1、算法+數(shù)據(jù)結(jié)構(gòu)=程序
2、智慧農(nóng)場(chǎng)監(jiān)測(cè)系統(tǒng)、入口處的紅外測(cè)溫、人臉識(shí)別程序等兩個(gè)程序應(yīng)用來說明算法效率的重要性。 四、算法效率分析 1、時(shí)間復(fù)雜度：指該算法的時(shí)間耗費(fèi)，是該算法中基本操作重復(fù)執(zhí)行的次數(shù)與問題規(guī)模n的某個(gè)函數(shù)。 （1） 四個(gè)實(shí)例練習(xí)及分析： 1+2+3+……+100=？算法一 1+2+3+……+100=？算法二 二維矩陣輸出 對(duì)分查找
分別計(jì)算執(zhí)行次數(shù)，得出時(shí)間復(fù)雜度
（2）總結(jié)大O表示法 （3）小結(jié)常用的時(shí)間復(fù)雜度。 2、空間復(fù)雜度：指該算法執(zhí)行所需要占用的存儲(chǔ)空間。（主要指臨時(shí)占用內(nèi)存空間） 空間復(fù)雜度(Space Complexity)是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時(shí)間復(fù)雜度是O(n2),空間復(fù)雜度是O(1) 。而一般的遞歸算法就要有O(n)的空間復(fù)雜度了，因?yàn)槊看芜f歸都要存儲(chǔ)返回信息。一個(gè)算法的優(yōu)劣主要從算法的執(zhí)行時(shí)間和所需要占用的存儲(chǔ)空間兩個(gè)方面衡量。高中階段主要考慮時(shí)間復(fù)雜度。 算法空間復(fù)雜度類似于時(shí)間復(fù)雜度，只是計(jì)算的不是運(yùn)行次數(shù)，而是在運(yùn)行過程中臨時(shí)變量被運(yùn)用次數(shù)。 五、比較數(shù)組和鏈表兩種不同的數(shù)據(jù)結(jié)構(gòu)對(duì)算法的影響。填寫表格 數(shù)組鏈表應(yīng)用場(chǎng)景組織結(jié)構(gòu)操作特性訪問：數(shù)據(jù)訪問效率較高
時(shí)間復(fù)雜度：________ 插入或刪除：需要移動(dòng)大量數(shù)組元素
時(shí)間復(fù)雜度：________訪問：需要從頭結(jié)點(diǎn)開始尋找
時(shí)間復(fù)雜度：________
插入或刪除：只要找出某個(gè)結(jié)點(diǎn)位置，可以方便操作
時(shí)間復(fù)雜度：________
六、課堂小結(jié) 七、自我評(píng)價(jià) 對(duì)自己的表現(xiàn)進(jìn)行客觀的評(píng)價(jià)，并思考后續(xù)完善的方向。（3=優(yōu)秀，2=一般，1=仍需加油） 評(píng)分項(xiàng)自我評(píng)價(jià)能以高斯問題為例認(rèn)識(shí)算法時(shí)間復(fù)雜度的概念 3 2 1能夠?qū)?jiǎn)單程序分析其算法時(shí)間復(fù)雜度 3 2 1能夠?qū)€性結(jié)構(gòu)的算法時(shí)間復(fù)雜度進(jìn)行簡(jiǎn)要分析 3 2 1能合理評(píng)估算法效率的重要性 3 2 1從此自覺將算法時(shí)間復(fù)雜度融入算法設(shè)計(jì)中 3 2 1
八、課后作業(yè) 1.度量某個(gè)算法效率高低的兩個(gè)方面： 、 。
2.分析右側(cè)流程圖算法的時(shí)間復(fù)雜度是（ ）： A.常數(shù)階 B.線性階 C.指數(shù)階 D.對(duì)數(shù)階 三、分析程序段的時(shí)間復(fù)雜度： 作業(yè)答案：
1.時(shí)間復(fù)雜度 空間復(fù)雜度
2.B
3.(1)O(1) (2)O(n)

展開更多......

收起↑