數(shù)據(jù)結構與算法學習筆記之 復雜度分析

數(shù)據(jù)結構與算法學習筆記之 復雜度分析

前言：

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

正文：復雜度分析

 一、什么是復雜度分析？

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

2.我們可以從執(zhí)行時間和占用空間來評估數(shù)據(jù)結構和算法的性能，也就空間復雜度、時間復雜度，統(tǒng)稱為復雜度。

3.復雜度描述的是算法執(zhí)行時間（或占用空間）與數(shù)據(jù)規(guī)模的增長關系。

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

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

2.掌握復雜度分析，將能編寫出性能更優(yōu)的代碼，有利于降低系統(tǒng)開發(fā)和維護成本。

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

1.大O表示法

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

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

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

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

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

2.復雜度分析法則

1）單段代碼看高頻：比如循環(huán)。

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

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

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

四、常用的復雜度級別？

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

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

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

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

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

一、概念：

1.最壞情況時間復雜度：代碼在最理想情況下執(zhí)行的時間復雜度。
2.最好情況時間復雜度：代碼在最壞情況下執(zhí)行的時間復雜度。
3.平均時間復雜度：用代碼在所有情況下執(zhí)行的次數(shù)的加權平均值表示。
4.均攤時間復雜度：在代碼執(zhí)行的所有復雜度情況中絕大部分是低級別的復雜度，個別情況是高級別復雜度且發(fā)生具有時序關系時，可以將個別高級別復雜度均攤到低級別復雜度上?；旧暇鶖偨Y果就等于低級別復雜度。

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

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

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

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

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

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

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

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

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

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

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