數據結構與算法學習筆記之 復雜度分析

數據結構與算法學習筆記之 復雜度分析

前言：

　 大家都知道數據結構和英語，就如同程序員的兩條腿一樣；只有不斷的積累，學習，擁有了健壯的“雙腿”才能越走越遠；在數據結構和算法的領域，不得不承認自己就是一只菜鳥；需要不斷的學習；在學習過程中，經常會有一些自己的看法，和別人獨特的見解；我都會一一做好筆記，以便進步；

正文：復雜度分析

 一、什么是復雜度分析？

1.數據結構和算法解決是“如何讓計算機更快時間、更省空間的解決問題”，而時間、空間復雜度做為數據結構和算法的精髓，很直觀說明了代碼”多快“”多省“。

2.我們可以從執行時間和占用空間來評估數據結構和算法的性能，也就空間復雜度、時間復雜度，統稱為復雜度。

3.復雜度描述的是算法執行時間（或占用空間）與數據規模的增長關系。

二、為什么要進行復雜度分析？

1.測試環境的不穩定因素（如同樣的代碼，i7比i3快得多），測試規模對測試結果影響很大（有些算法更適用于大規模數據），復雜度分析有不依賴執行環境、成本低、效率高、易操作、指導性強的特點。

2.掌握復雜度分析，將能編寫出性能更優的代碼，有利于降低系統開發和維護成本。

三、如何進行復雜度分析？

1.大O表示法

1）所有代碼的執行時間 T(n) 與每行代碼的執行次數 n 成正比

　　T(n) = O(f（n）)

其中T(n)表示算法執行總時間，f(n)表示每行代碼執行總次數，而n往往表示數據的規模。

大 O 時間復雜度并不具體表示代碼真正的執行時間，而是表示代碼執行時間隨數據規模增長的變化趨勢，也叫作漸進時間復雜度，簡稱時間復雜度，

常量階、低階以及系數實際上對這種增長趨勢不產決定性影響，所以在做時間復雜度分析時忽略這些項。

2.復雜度分析法則

1）單段代碼看高頻：比如循環。

2）多段代碼取最大：比如一段代碼中有單循環和多重循環，那么取多重循環的復雜度。

3）嵌套代碼求乘積：比如遞歸、多重循環等

4）多個規模求加法：比如方法有兩個參數控制兩個循環的次數，那么這時就取二者復雜度相加。

四、常用的復雜度級別？

多項式階：隨著數據規模的增長，算法的執行時間和空間占用，按照多項式的比例增長。包括， O(1)（常數階）、O(logn)（對數階）、O(n)（線性階）、O(nlogn)（線性對數階）、O(n^2)（平方階）、O(n^3)（立方階）

非多項式階：隨著數據規模的增長，算法的執行時間和空間占用暴增，這類算法性能極差。包括， O(2^n)（指數階）、O(n!)（階乘階）

五、如何掌握好復雜度分析方法？

復雜度分析關鍵在于多練，所謂孰能生巧。

六、最好、最壞、平均、均攤時間復雜度

一、概念：

1.最壞情況時間復雜度：代碼在最理想情況下執行的時間復雜度。
2.最好情況時間復雜度：代碼在最壞情況下執行的時間復雜度。
3.平均時間復雜度：用代碼在所有情況下執行的次數的加權平均值表示。
4.均攤時間復雜度：在代碼執行的所有復雜度情況中絕大部分是低級別的復雜度，個別情況是高級別復雜度且發生具有時序關系時，可以將個別高級別復雜度均攤到低級別復雜度上。基本上均攤結果就等于低級別復雜度。

二、為什么要引入這4個概念？

1.同一段代碼在不同情況下時間復雜度會出現量級差異，為了更全面，更準確的描述代碼的時間復雜度，所以引入這4個概念。
2.代碼復雜度在不同情況下出現量級差別時才需要區別這四種復雜度。大多數情況下，是不需要區別分析它們的。

三、如何分析平均、均攤時間復雜度？

1.平均時間復雜度
代碼在不同情況下復雜度出現量級差別，則用代碼所有可能情況下執行次數的加權平均值表示。
2.均攤時間復雜度
兩個條件滿足時使用：1）代碼在絕大多數情況下是低級別復雜度，只有極少數情況是高級別復雜度；2）低級別和高級別復雜度出現具有時序規律。均攤結果一般都等于低級別復雜度。

 有人說，我們項目之前都會進行性能測試，再做代碼的時間復雜度、空間復雜度分析，是不是多此一舉呢？

每段代碼都分析一下時間復雜度、空間復雜度，是不是很浪費時間呢？

我不認為是多此一舉，漸進時間，空間復雜度分析為我們提供了一個很好的理論分析的方向，并且它是宿主平臺無關的，能夠讓我們對我們的程序或算法有一個大致的認識，讓我們知道，比如在最壞的情況下程序的執行效率如何，同時也為我們交流提供了一個不錯的橋梁，我們可以說，算法1的時間復雜度是O(n)，算法2的時間復雜度是O(logN)，這樣我們立刻就對不同的算法有了一個“效率”上的感性認識。

當然，漸進式時間，空間復雜度分析只是一個理論模型，只能提供給粗略的估計分析，我們不能直接斷定就覺得O(logN)的算法一定優于O(n), 針對不同的宿主環境，不同的數據集，不同的數據量的大小，在實際應用上面可能真正的性能會不同，個人覺得，針對不同的實際情況，進而進行一定的性能基準測試是很有必要的，比如在統一一批手機上(同樣的硬件，系統等等)進行橫向基準測試，進而選擇適合特定應用場景下的最有算法。

綜上所述，漸進式時間，空間復雜度分析與性能基準測試并不沖突，而是相輔相成的，但是一個低階的時間復雜度程序有極大的可能性會優于一個高階的時間復雜度程序，所以在實際編程中，時刻關心理論時間，空間度模型是有助于產出效率高的程序的，同時，因為漸進式時間，空間復雜度分析只是提供一個粗略的分析模型，因此也不會浪費太多時間，重點在于在編程時，要具有這種復雜度分析的思維。

歡迎大家關注公眾號，不定時干貨，只做有價值的輸出

作者：Dawnzhang 
出處：https://www.cnblogs.com/clwydjgs/p/9718754.html 
版權：本文版權歸作者
轉載：歡迎轉載，但未經作者同意，必須保留此段聲明；必須在文章中給出原文連接；否則必究法律責任