數(shù)據(jù)結(jié)構(gòu)與算法效率課件-2024-2025學(xué)年浙教版（2019）高中信息技術(shù)選修一

數(shù)據(jù)結(jié)構(gòu)與算法效率情境導(dǎo)入

高斯是一位杰出的天文學(xué)家、數(shù)學(xué)家和物理學(xué)家。傳說在他還是個(gè)小孩子的時(shí)候，有一次數(shù)學(xué)課上，老師布置了一道特別繁瑣的加法題：計(jì)算從1加到100的總和。其他學(xué)生都在一步一步地計(jì)算，1+2=3，3+3=6，6+4=10，而年幼的高斯不一會(huì)兒就報(bào)告了答案——5050。數(shù)學(xué)老師很驚訝，高斯居然可以在這么短的時(shí)間內(nèi)算出正確答案。效率算法效率算法效率的高低可由算法復(fù)雜度來度量。時(shí)間復(fù)雜度：反映了算法執(zhí)行所需要的時(shí)間空間復(fù)雜度：反映了算法執(zhí)行所需要占用的存儲(chǔ)空間活動(dòng)：測(cè)量運(yùn)行時(shí)間

對(duì)算法進(jìn)行實(shí)際運(yùn)行測(cè)試，獲得真實(shí)的運(yùn)行時(shí)間?？梢酝ㄟ^Python的time模塊，記錄算法開始前和結(jié)束后的系統(tǒng)時(shí)間，其差值就是運(yùn)行時(shí)間。importtimestart=time.time()#在此處添加需要執(zhí)行的程序end=time.time()print("%.10f"%(end-start))#算法開始前的系統(tǒng)時(shí)間#算法結(jié)束后的系統(tǒng)時(shí)間#計(jì)算差值并保留10位小數(shù)活動(dòng)：測(cè)量運(yùn)行時(shí)間defsum1(n):sum=0foriinrange(1,n+1):sum=sum+ireturnsum算法1（其他同學(xué)計(jì)算方法）defsum2(n):sum=n*(n+1)/2returnsum算法2（高斯計(jì)算方法）1.連續(xù)運(yùn)行算法1和算法2五次，并記錄每次運(yùn)行時(shí)間。2.改變變量n的值，觀察運(yùn)行時(shí)間的變化情況。對(duì)比得到的數(shù)據(jù)，可以觀察出什么結(jié)論？第1次第2次第3次第4次第5次n=

100004.3×10-44.6×10-42.7×10-42.7×10-42.7×10-4n=

1000003.4×10-33.1×10-33.1×10-33.0×10-33.0×10-3n=

10000003.2×10-23.1×10-23.0×10-23.1×10-23.0×10-2第1次第2次第3次第4次第5次n=

100002.1×10-60.9×10-6000n=

100000000.9×10-600n=

1000000000.9×10-600算法1算法2

同一個(gè)算法，不同計(jì)算機(jī)設(shè)備運(yùn)行時(shí)間會(huì)不相同，除此之外，用不同編程語言編寫同一個(gè)算法，得到的運(yùn)行時(shí)間也會(huì)不相同。這都是外部環(huán)境對(duì)算法運(yùn)行時(shí)間的影響。不僅如此，有些算法無法先運(yùn)行，事后統(tǒng)計(jì)運(yùn)行時(shí)間，比如導(dǎo)彈控制算法。所以單純的用執(zhí)行時(shí)間來評(píng)估算法效率是不妥當(dāng)?shù)摹３?jí)計(jì)算機(jī)單片機(jī)三張圖均為AI生成模擬導(dǎo)彈控制情境

我們要找一種不需要運(yùn)行程序，且與外界因素?zé)o關(guān)的度量指標(biāo)來評(píng)估算法的執(zhí)行時(shí)間。

代碼語句一段代碼的執(zhí)行時(shí)間每條語句執(zhí)行時(shí)間的總和一條語句執(zhí)行時(shí)間相同語句的總執(zhí)行次數(shù)

defsum1(n):sum=0foriinrange(1,n+1):

sum=sum+ireturnsum語句總執(zhí)行次數(shù)①②③④#執(zhí)行1次#執(zhí)行n次#執(zhí)行n次#執(zhí)行1次

算法1（其他同學(xué)計(jì)算方法）

問題規(guī)模

指處理問題的大小。問題規(guī)模是影響算法執(zhí)行時(shí)間的主要因素defsum1(n):

sum=0

foriinrange(1,n+1):

sum=sum+i

returnsum算法1（其他同學(xué)計(jì)算方法）defsum2(n):

sum=n*(n+1)/2

returnsum算法2（高斯計(jì)算方法）①②①②③④語句總執(zhí)行次數(shù)

大O記法大O記法推導(dǎo)大O階的方法：1.用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。2.在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。3.如果最高階項(xiàng)存在且不是1,那么去除與這個(gè)項(xiàng)相乘的常數(shù)。得到的結(jié)果就是大O階。

保留最高階項(xiàng)

去除常數(shù)

小試牛刀例1.該程序的時(shí)間復(fù)雜度是：n=int(input())s=0x=0foriinrange(1,n+1):

forjinrange(1,n+1):

x=x+1

s=s+xprint(s)小試牛刀例2.該程序的時(shí)間復(fù)雜度是：deff(n):s=0i=1

whilei<=n:

s=s+i

i=i*2returnsprint(f(4))關(guān)注循環(huán)執(zhí)行次數(shù)

......

執(zhí)行次數(shù)：

k<log2n

×2×2×2×2×2

sum=sum+i算法1

x=x+1

s=s+x例1whilei<=n:

s=s+i

例2

<<i=i*2foriinrange(1,n+1):foriinrange(1,n+1):

forjinrange(1,n+1):i=i+1foriinrange(1,n+1):

sum=sum+iforiinrange(1,n+1):

forjinrange(1,n+1):

x=x+1

s=s+xwhilei<=n:

s=s+i

i=i*2

問題2:

在將三段代碼拼接后，新代碼段的時(shí)間復(fù)雜度是多少？

常見時(shí)間復(fù)雜度耗時(shí)比較在分析算法效率的過程中，為了判斷哪一項(xiàng)是起主導(dǎo)作用的，需要了解常見函數(shù)中n變大的情況下的差異性，下圖展示了常見函數(shù)的增長(zhǎng)情況。

常數(shù)階對(duì)數(shù)階線性階對(duì)數(shù)線性階平方階立法階指數(shù)階階乘階此圖原創(chuàng)【思考】未來在設(shè)計(jì)算法的時(shí)候如何降低時(shí)間復(fù)雜度。

算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨問題規(guī)模增長(zhǎng)而增長(zhǎng)的量級(jí)，在很大程度上能很好地反映出算法的優(yōu)劣?！舅伎肌课磥碓谠O(shè)計(jì)算法的時(shí)候如何降低時(shí)間復(fù)雜度。

設(shè)計(jì)算法時(shí)，盡量減少循環(huán)的嵌套。調(diào)用函數(shù)減少重復(fù)計(jì)算。

算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨問題規(guī)模增長(zhǎng)而增長(zhǎng)的量級(jí)，在很大程度上能很好地反映出算法的優(yōu)劣。程序=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)對(duì)算法效率的影響數(shù)組鏈表訪問通過下標(biāo)獲取數(shù)據(jù)時(shí)間復(fù)雜度：________需要從頭結(jié)點(diǎn)遍歷尋找，直到找到目標(biāo)節(jié)點(diǎn)時(shí)間復(fù)雜度：_______

如果需要頻繁地訪問數(shù)據(jù)元素，則優(yōu)先選擇數(shù)組。數(shù)組訪問鏈表訪問

以我們?cè)?jīng)學(xué)習(xí)過的數(shù)組和鏈表為例，回憶元素訪問、插入、刪除方面的效率差異，并完成下列表格：數(shù)組鏈表插入、刪除需要移動(dòng)大量數(shù)組元素以保持?jǐn)?shù)組的連續(xù)性時(shí)間復(fù)雜度：________只要找出某個(gè)結(jié)點(diǎn)位置，直接改變指針時(shí)間復(fù)雜度：________

數(shù)組插入數(shù)組刪除數(shù)據(jù)結(jié)構(gòu)對(duì)算法效率的影響如果需要頻繁地執(zhí)行插入刪除操作，則優(yōu)先選擇鏈表。鏈表插入鏈表刪除數(shù)組鏈表插入、刪除需要移動(dòng)大量數(shù)組元素以保持?jǐn)?shù)組的連續(xù)性時(shí)間復(fù)雜度：________只要找出某個(gè)結(jié)點(diǎn)位置，直接改