資源簡介

(共20張PPT)
5.1 數據結構與算法效率
冊 別：選擇性必修1
學 科：高中信息技術（浙教版）
學習目標：
能理解數據結構與算法的關系。
能認識算法效率高低的主要的兩個方面：時間復雜度與空間復雜度，及這兩個方面的表示與計算。
能通過具體的實例分析算法的效率。
逐步自覺將算法的效率應用在算法程序設計中，根據問題選擇合適的數據結構，提高算法效率。
能通過具體的實例認識算法效率的重要性。
情境導入
Google實驗
搜索引擎是互聯網上的檢索技術，它能提高人們獲取搜集信息的速度，為人們提供更好的網絡使用環境，Google做過一個試驗，顯示10條搜索結果的頁面載入需要0.4秒，顯示30條搜索結果的頁面載入需要0.9秒，結果后者使得Google總的流量和收入減少了20%。Google地圖上線的時候，首頁大小有100KB，后來下降到70~80KB。結果，流量在第一個星期上升了10%，接下來的3個星期又再上升了25%。 Amazon（亞馬遜公司）的統計也顯示了相近的結果，首頁打開時間每增加100毫秒，網站銷售量會減少1%。
資料來源：互聯網
算法+數據結構=程序
算法：解析法、枚舉法、遞歸、迭代、排序、查找等
數據結構：數組、鏈表、隊列、棧、字符串、樹等
著名的計算機科學家、圖靈獎獲得者尼克勞斯 沃思（Niklaus Wirth）指出
（Algorithm+Data Structures=Programs）
算法依賴數據結構，算法與數據結構為程序服務，達成問題解決
算法效率重要性分析
智慧農場監測系統、氣象預報程序必須在指定時間前完成。如果不能按時計算出預報結果，這個算法有價值嗎？
入口處的紅外測溫、人臉識別程序，必須在幾分之一秒內完成工作。過慢的算法會帶來糟糕的用戶體驗，這樣的設備有可能廣泛采用嗎？
實例分析：
“數學王子”高斯小時候，老師給從未上過算術課的同學們布置了一道題目：1+2+3+……+100=？
其他同學在仔細算題時，高斯快速巧妙地解決了問題，老師對他刮目相看。他的算法被稱為“高斯算法”。
源于教材P116例子
算法效率分析
算法的效率
時間復雜度
空間復雜度
指該算法的時間耗費，是該算法中基本操作重復執行的次數與問題規模n的某個函數。
指該算法執行所需要占用的存儲空間。
（主要指臨時占用內存空間）
算法效率分析:高斯算法
時間復雜度
n=int(input())
s=(1+n)*n/2
print(s)
#執行1次
1+2+3+……+100=？算法一
#執行1次
#執行1次
該程序采用的推導方法：通過加法計算該程序運行了常數3次，用常數1取代運行時間中的所有加法常數。
O(1)
常量階
算法效率分析:高斯算法
時間復雜度
1+2+3+……+100=？算法二
n=int(input())
s=0 for i in range(1,n+1):
s=s+i
print(s)
#執行1次
#執行1次
#執行n次
#執行n次
#執行1次
通過加法計算該程序運行了常數2n+3次，修改運行次數函數，只保留最高階項，由于最高階系數不是1，去除這個項的相乘系數2。
O(n)
線性階
算法效率分析:輸出二維矩陣算法
時間復雜度
n=int(input())
for i in range(1,n+1):
for j in range(1,n+1):
x=random.randint(10,99)
print(x,end=””)
#執行1次
#執行n次
#執行n*n次
#執行n*n次
#執行n*n次
該程序段中包含二重循環，通過乘法計算該二重循環程序運行了n*n次，該算法中語句的執行次數與問題規模n呈平方增大。
O(n2)
平方階
算法效率分析:對分查找算法
時間復雜度
i=0;n=len(d);j=n-1
while i<=j:
m=(i+j)//2
if key>=d[m]:
j=m-1
else:
i=m+1
#執行3次
#執行<=log2n+2次
#執行<=log2n+1次
該二分查找在最壞的情況下查找次數依次是n/2,n/4,n/8…… 一直到1為止，我們假設是x次才能查找到目標數。所以可以根據題意列出下面等式：n(1/2)x = 1
O(log2n)
對數階
→2x=n
→x=log2n
大O表示法
用O()來體現算法時間復雜度，稱之為大O表示法。其推導方法如下：
1.用常數1取代運行時間中的所有加法常數。
2.在修改后的運行次數函數中，只保留最高階項。
3.如果最高階項存在且不是1，那么去除與這個項相乘數的常數。得到的結果就是大O階。
例如： n(n-1)
→ n2
保留最高階項
→ n2
去除常數項
課堂小練
算式： 15n2＋12n＋9，時間復雜度其大O階為（ ）
15n2＋12n＋9大O階推導過程：
O(n2)
(常數1取代加法常數）→15n2＋12n
(保留高階)→15n2
(去除高階相乘常數)→n2
因此該算式的大O階(時間復雜度)為O(n2)。
課堂上機操作實驗：
#程序一
import time
s = 0 #執行1次
n = 2 * 10 ** 4
start = time.time()
for i in range(1,n + 1): #執行n次
s = s + 1 #執行n次
print(s)
end = time.time()
print(end - start)
#程序二
import time
s = 0
n = 2 * 10 ** 4
start = time.time()
for i in range(1,n + 1): #執行n次
for j in range(1,n + 1):
s = s + 1 #執行n * n次
print(s)
end = time.time()
print(end - start)
大O表示法具體實例
時間復雜度所耗費的時間是：
執行次數函數 階 術語描述
16 ｏ(1) 常量階
3n+6 ｏ(n) 線性階
5n2+5n+6 ｏ(n2) 平方階
7log2n+18 ｏ(log2n) 對數階
8n3+8n2+8n+6 ｏ(n3) 立方階
3n ｏ(3n) 指數階
O(1)常見函數的增長率
問題討論：舉例說明空間復雜度的度量
空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時間復雜度是O(n2),空間復雜度是O(1) 。而一般的遞歸算法就要有O(n)的空間復雜度了，因為每次遞歸都要存儲返回信息。一個算法的優劣主要從算法的執行時間和所需要占用的存儲空間兩個方面衡量。高中階段主要考慮時間復雜度。
算法空間復雜度類似于時間復雜度，只是計算的不是運行次數，而是在運行過程中臨時變量被運用次數。
（學習118頁完善表格）
數據結構對算法效率的影響
數組 鏈表
應用場景
組織結構
操作特性 訪問：數據訪問效率較高 時間復雜度：________ 插入或刪除：需要移動大量數組元素 時間復雜度：________ 訪問：需要從頭結點開始尋找
時間復雜度：________
插入或刪除：只要找出某個結點位置，可以方便操作
時間復雜度：________
O(1)
O(n)
O(n)
O(1)
適合數據規模確定且在處理過程中保持數據規模穩定的問題
不需要預先分配存儲空間，結點個數不受限制
用一段連續的存儲單元來依次存儲數組元素
由結點構成，每個結點中包含數據區域和指針區域，相鄰結點間通過指針鏈接
課堂小結
算法的效率
時間復雜度 空間復雜度
數據結構與算法的關系
數組、鏈表不同操作的時間復雜度
算法效率的重要性
學習評價
對自己的表現進行客觀的評價，并思考后續完善的方向。（3=優秀，2=一般，1=仍需加油）
評分項 自我評價
能以高斯問題為例認識算法時間復雜度的概念 3 2 1
能夠對簡單程序分析其算法時間復雜度 3 2 1
能夠對線性結構的算法時間復雜度進行簡要分析 3 2 1
能合理評估算法效率的重要性 3 2 1
從此自覺將算法時間復雜度融入算法設計中 3 2 1
課后作業
1.度量某個算法效率高低的兩個方面： 、 。
2.分析右側流程圖算法的時間復雜度是（ ）：
A.常量階 B.線性階 C.指數階 D.對數階
（1）a=int(input())
b=int(input())
if a>b:
max=a
else:
max=b
（2）n=int(input())
i=1;s=1
while i<=n:
s=s*i
i+=1
3.分析程序段的時間復雜度：

展開更多......

收起↑