資源簡介

(共17張PPT)
數據結構與算法效率
數據結構指的是數據之間的相互關系，即數據組織形式。包括：邏輯結構、存儲結構、基本操作（數據運算）。
數據結構概念及類型
常見類型：數組、鏈表、隊列、棧、樹和圖等。
同一個問題若采用不同的數據結構，算法效率也將不同。
算法效率是指算法執行的時間，算法執行時間需通過依據該算法編制的程序在計算機上運行時所消耗的時間來度量。
活動一：求和問題的效率探討
求1+2+3+……+n的和
算法一：高斯求和
n=int(input())
s=(1+n)*n/2
print(s)
例
算法二：累加求和
n=int(input())
s=0
for i in range(1,n+1): s=s+i
print(s)
這兩種算法的執行效率一樣嗎？
算法效率的度量方式
方法一：可依據該算法編制的程序在計算機上運行時所消耗的時間來度量；
方法二：算法效率的高低也可由算法復雜度來度量。
利用計算機的計時功能，對不同算法編制的程序的運行時間進行比較。
方法一：計算算法執行所需時間度量算法效率。
算法一:高斯求和
import time
start = time.time()
n=int(input())
s=(1+n)*n/2
print(s)
end = time.time()
print(end - start)
算法二:累加求和
import time
start = time.time()
n=int(input())
s=0
for i in range(1,n+1): s=s+i
print(s)
end = time.time()
print(end - start)
任務要求
執行算法一和算法二的程序，輸入不同的n,并將運行時間記錄在任務單上，比較分析兩種算法的算法效率。
結 論
當輸入的問題規模n大到一定程度，高斯求和的運行時間低于累加求和算法，
高斯求和的算法效率高。
算法復雜度分為時間復雜度和空間復雜度。
方法二：預估算法復雜度度量算法效率
時間復雜度: 指該算法中基本操作重復執行的次數與問題規模n的某個函數。
空間復雜度:指該算法在運行過程中臨時占用存儲空間大小的度量。
算法時間復雜度的表示
算法一:高斯求和
n=int(input())
s=(1+n)*n/2
print(s)
算法二:累加求和
n=int(input())
s=0
for i in range(1,n+1): s=s+i
print(s)
#執行1次
#執行1次
#執行1次
執行次數T(n)=3
執行次數T(n)=2n+3
#執行1次
#執行1次
#執行n次
#執行n次
#執行1次
時間復雜度常用符號O表示，記作: O(T(n))
它表示隨著問題規模n的增大，算法執行時間的增長率和T(n)的增長率相同
算法時間復雜度的表示
算法一：高斯求和
T(n)=3
O(3)
O(1)
常量階
算法二：累加求和
T(n)=2n+3
O(2n+3)
O(2n+1)
線性階
O(n)
O(2n)
結論
時間效率:O(1)試一試：推導算法時間復雜度
n=int(input())
s=0
x=0
for i in range(1,n+1):
for j in range(1,n+1):
x=x+1
s=s+x
print(s)
#執行1次
#執行1次
#執行1次
#執行n次
#執行n*n次
#執行n*n次
#執行n*n次
#執行1次
算法時間復雜度：
O(3n2+n+4)
O(3n2+n+1)
O(3n2)
O(n2)
平方階
常見的算法時間復雜度
階 術語
O(1) 常量階
O(n) 線性階
O(n2) 平方階
O(log2n) 對數階
O(n3) 立方階
O(2n) 指數階
算法的時間復雜度反映了程序執行時間隨問題規模增長而增長的量級。
活動二：數據結構對算法效率的影響
數據結構 邏輯結構 存儲結構 基本操作
數組 確定 連續 增、刪、改、查
鏈表 確定 不連續 增、刪、改、查
數據結構 查看第n個元素的時間復雜度 插入、刪除元素時間復雜度
數組
鏈表
head
移動
O(1)
O(n)
O(n)
O(1)
試一試：計算斐波那契數列的第n項
數學家斐波那契在他的《算盤書》里排了一個數列:1,1,2,3,5……這個數列可以和黃金分割聯系起來。這個數列越排到后面,前一個數與后一個數的比值就越接近0.618(34/55約等于0.618),就是黃金分割的近似值。請編寫了一個程序來計算并輸出斐波那契數列的第n項。
試一試：計算斐波那契數列的第n項
a=[0]*20000001
n=int(input("請輸人一個正整數:"))
a[1]=1
a[2]=1
for i in range(3,n+1):
a[i]=a[i-1]+a[i-2]
print(a[n])
算法一
算法二
n=int( input("請輸入一個正整數:"))
a=b=1
for i in range(3,n+1):
c=a+b #當前項的值等于前兩項的和
a=b
b=c
print(c)
算法一和算法二時間復雜度相同，均為O(n)
算法一的空間復雜度>算法二的空間復雜度
1.你知道空間復雜度是如何度量的嗎？
2.有人認為現代計算機的運行速度足夠快了，已經沒有必要研究算法的效率了，你有什么體會？
拓展思考
1 算法效率度量的一般方法
時間復雜度和空間復雜度
2 數據結構與算法效率的關系
數組、鏈表不同操作的時間復雜度
3 算法效率評估
合理評估算法效率的重要性
課堂小結
評分項 自我評價 同學互評
能完成新課導入中的問題并建立算法時間復雜度的概念 5 4 3 2 1 5 4 3 2 1
能夠對簡單程序分析其算法時間復雜度 5 4 3 2 1 5 4 3 2 1
能夠對線性結構的算法時間復雜度進行簡要分析 5 4 3 2 1 5 4 3 2 1
能合理評估算法效率的重要性 5 4 3 2 1 5 4 3 2 1
對自己和同伴的表現進行客觀的評價，并思考后續完善的方向。（5=優秀，4=超出一般水平，3=滿意，2=有待改進，1=不太理想）
謝謝觀看！

展開更多......

收起↑