第2章算法復(fù)雜度2025/6/111主要內(nèi)容●算法●算法的復(fù)雜度

●常見(jiàn)的復(fù)雜度2.1算法算法(algorithm)就是一個(gè)正確的計(jì)算過(guò)程，該過(guò)程取某個(gè)值或值的集合作為輸入并產(chǎn)生某個(gè)值或值的集合作為輸出。2025/6/1122025/6/113算法的4個(gè)主要特性：2.1算法算法的4個(gè)主要特性是：●確切性：算法由語(yǔ)句組成，每個(gè)語(yǔ)句的功能是確切的。●輸入數(shù)據(jù)：可以向算法輸入多個(gè)或0個(gè)數(shù)據(jù)（方法可以有參數(shù)或無(wú)參數(shù)），即算法可以接收或不接收外部數(shù)據(jù)?！褫敵鰯?shù)據(jù)：算法可以給出明確的計(jì)算結(jié)果（方法的返回值）或輸出若干數(shù)據(jù)到客戶端以反映算法產(chǎn)生的效果?！窨尚行裕夯静僮鞫际窃谟邢迺r(shí)間內(nèi)被完成。所謂有限時(shí)間是指這個(gè)時(shí)值僅僅依賴于特定的硬件設(shè)施，不依賴于一個(gè)正整數(shù)n，即不會(huì)隨著n的增加而增大?！翊_切性●輸入數(shù)據(jù)●輸出數(shù)據(jù)●可行性2025/6/114一個(gè)算法不能在有限的時(shí)間內(nèi)結(jié)束，就不屬于算法復(fù)雜度的研究的范疇，比如一個(gè)算法里出現(xiàn)的無(wú)限循環(huán)，就不再屬于算法復(fù)雜度的研究的范疇了2.2復(fù)雜度算法，從執(zhí)行到結(jié)束，涉及兩個(gè)度量：一個(gè)是執(zhí)行方法所消耗的時(shí)間，一個(gè)是執(zhí)行方法所需要的內(nèi)存空間。2025/6/115方法里聲明的局部變量，包括參數(shù)都不歸類到基本操作，即不是基本操作。2.2復(fù)雜度⒈基本操作一個(gè)基本操作是一個(gè)語(yǔ)句或一個(gè)運(yùn)算表達(dá)式。一個(gè)基本操作是一條語(yǔ)句或一個(gè)運(yùn)算表達(dá)式，而且必須是在有限時(shí)間內(nèi)能被完成的計(jì)算步驟，其耗時(shí)僅僅依賴于特定的硬件設(shè)施，不依賴于一個(gè)正整數(shù)n，不會(huì)隨著n的增加而增大。2025/6/116在計(jì)算算法執(zhí)行的基本操作的總數(shù)時(shí)，要真對(duì)最壞的情況，即在某種條件下執(zhí)行的基本操作的總數(shù)是最多的情況2.2復(fù)雜度3時(shí)間復(fù)雜度算法執(zhí)行的基本操作的總數(shù)T(n)。算法的復(fù)雜度主要是度量隨著n的增大，T(n)值的趨勢(shì)。2025/6/117學(xué)習(xí)復(fù)雜度，記住一個(gè)通俗的道理：時(shí)間累加，空間不累加.2.2復(fù)雜度4復(fù)雜度比較2025/6/1182.3常見(jiàn)復(fù)雜度⒈O(jiān)(1)復(fù)雜度算法中的基本操作被執(zhí)行的總次數(shù)是一個(gè)常量，即不依賴一個(gè)正整數(shù)n、不會(huì)隨著n的增加而增大，那么將算法的時(shí)間復(fù)雜度，記作O(1)。算法中的所占用的內(nèi)存是一個(gè)常量，即所占內(nèi)存不依賴一個(gè)正整數(shù)n、不會(huì)隨著n的增加而增大，那么將算法的空間復(fù)雜度，記作O(1)。

例子1計(jì)算最大值A(chǔ)LG2_1.pych2_1.py2025/6/1192.3常見(jiàn)復(fù)雜度1.O(1)復(fù)雜度

sum()函數(shù)中return語(yǔ)句被執(zhí)行了一次，range(1,101)被重復(fù)執(zhí)行了101次，賦值語(yǔ)句“sum_result+=i;”重復(fù)了100次。那么算法中的基本操作被執(zhí)行的總數(shù)是202，是一個(gè)常量，因此時(shí)間復(fù)雜度是O(1)。sum()函數(shù)中有兩個(gè)局部變量sum_result和i，而兩個(gè)變量占用內(nèi)存的大小都是固定的，因此空間復(fù)雜度是O(1).

ALG2_2.py

ch2_2.py2025/6/11102.3常見(jiàn)復(fù)雜度2.O(n)復(fù)雜度

2025/6/11112.3常見(jiàn)復(fù)雜度2.O(n)復(fù)雜度

ALG2_3.py

ch2_3.py

2025/6/11122.3常見(jiàn)復(fù)雜度2.O(n)復(fù)雜度例子4求數(shù)組元素的最大值A(chǔ)LG2_4.py

ch2_4.py

2025/6/11132.3常見(jiàn)復(fù)雜度2.O(n)復(fù)雜度例子5尋找缺失的一個(gè)自然數(shù)ALG2_5.pych2_5.py例子5尋找缺失的一個(gè)自然數(shù)

2025/6/11142.3常見(jiàn)復(fù)雜度2.O(n)復(fù)雜度例子5

find_missing_number(inta[],intlength)算法中的基本操作不是加法和減法，而是使用了異或^運(yùn)算。

find_number(arr,length)的算法和前面兩者不同，算法使用的是窮舉法，算法中的for語(yǔ)句里嵌套了for語(yǔ)句形成的雙層循環(huán)，不難驗(yàn)證其時(shí)間復(fù)雜度是O(n^2)。ALG2_5.py2025/6/11152.3常見(jiàn)復(fù)雜度3.2025/6/11162.3常見(jiàn)復(fù)雜度3.

ALG2_6.py

ch2_6.py

2025/6/11172.3常見(jiàn)復(fù)雜度3.例子7起泡法排序ALG2_7.py

ch2_7.py2025/6/11182.3常見(jiàn)復(fù)雜度4.

2025/6/11192.3常見(jiàn)復(fù)雜度4.例子8ALG2_8.py

ch2_8.py

2025/6/11202.3常見(jiàn)復(fù)雜度5.

2025/6/11212.3常見(jiàn)復(fù)雜度5.例子9二分法ALG2_9.py

ch2_9.py

2025/6/11222.3常見(jiàn)復(fù)雜度5.例子10歐幾里得算法ALG2_10.pych2_10.py

2025/6/11232.3常見(jiàn)復(fù)雜度6.

如果一個(gè)函數(shù)里又調(diào)用了其它函數(shù)，即一個(gè)算法又包含另外一個(gè)算法，那么該函數(shù)的復(fù)雜度將和它包含的函數(shù)復(fù)雜度有關(guān)，需合并考察復(fù)雜度。

2025/6/11242.3常見(jiàn)復(fù)雜度6.例子11使用二分法查找一個(gè)數(shù)組在另一個(gè)數(shù)組中的值

ALG2_11.py

ch2_11.py

2025/6/11252.3常見(jiàn)復(fù)雜度6.例子12數(shù)組所