數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之復(fù)雜度分析-創(chuàng)新互聯(lián)
大家都知道數(shù)據(jù)結(jié)構(gòu)和英語(yǔ)，就如同程序員的兩條腿一樣；只有不斷的積累，學(xué)習(xí)，擁有了健壯的“雙腿”才能越走越遠(yuǎn)；在數(shù)據(jù)結(jié)構(gòu)和算法的領(lǐng)域，不得不承認(rèn)自己就是一只菜鳥(niǎo)；需要不斷的學(xué)習(xí)；在學(xué)習(xí)過(guò)程中，經(jīng)常會(huì)有一些自己的看法，和別人獨(dú)特的見(jiàn)解；我都會(huì)一一做好筆記，以便進(jìn)步；
正文：復(fù)雜度分析 一、什么是復(fù)雜度分析？1.數(shù)據(jù)結(jié)構(gòu)和算法解決是“如何讓計(jì)算機(jī)更快時(shí)間、更省空間的解決問(wèn)題”，而時(shí)間、空間復(fù)雜度做為數(shù)據(jù)結(jié)構(gòu)和算法的精髓，很直觀說(shuō)明了代碼”多快“”多省“。
2.我們可以從執(zhí)行時(shí)間和占用空間來(lái)評(píng)估數(shù)據(jù)結(jié)構(gòu)和算法的性能，也就空間復(fù)雜度、時(shí)間復(fù)雜度，統(tǒng)稱(chēng)為復(fù)雜度。
3.復(fù)雜度描述的是算法執(zhí)行時(shí)間（或占用空間）與數(shù)據(jù)規(guī)模的增長(zhǎng)關(guān)系。
二、為什么要進(jìn)行復(fù)雜度分析？1.測(cè)試環(huán)境的不穩(wěn)定因素（如同樣的代碼，i7比i3快得多），測(cè)試規(guī)模對(duì)測(cè)試結(jié)果影響很大（有些算法更適用于大規(guī)模數(shù)據(jù)），復(fù)雜度分析有不依賴(lài)執(zhí)行環(huán)境、成本低、效率高、易操作、指導(dǎo)性強(qiáng)的特點(diǎn)。
2.掌握復(fù)雜度分析，將能編寫(xiě)出性能更優(yōu)的代碼，有利于降低系統(tǒng)開(kāi)發(fā)和維護(hù)成本。
三、如何進(jìn)行復(fù)雜度分析？1.大O表示法1）所有代碼的執(zhí)行時(shí)間 T(n) 與每行代碼的執(zhí)行次數(shù) n 成正比
T(n) = O(f（n）)其中T(n)表示算法執(zhí)行總時(shí)間，f(n)表示每行代碼執(zhí)行總次數(shù)，而n往往表示數(shù)據(jù)的規(guī)模。
大 O 時(shí)間復(fù)雜度并不具體表示代碼真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，也叫作漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度，
常量階、低階以及系數(shù)實(shí)際上對(duì)這種增長(zhǎng)趨勢(shì)不產(chǎn)決定性影響，所以在做時(shí)間復(fù)雜度分析時(shí)忽略這些項(xiàng)。
2.復(fù)雜度分析法則1）單段代碼看高頻：比如循環(huán)。
2）多段代碼取大：比如一段代碼中有單循環(huán)和多重循環(huán)，那么取多重循環(huán)的復(fù)雜度。
3）嵌套代碼求乘積：比如遞歸、多重循環(huán)等
4）多個(gè)規(guī)模求加法：比如方法有兩個(gè)參數(shù)控制兩個(gè)循環(huán)的次數(shù)，那么這時(shí)就取二者復(fù)雜度相加。
四、常用的復(fù)雜度級(jí)別？多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長(zhǎng)，算法的執(zhí)行時(shí)間和空間占用，按照多項(xiàng)式的比例增長(zhǎng)。包括， O(1)（常數(shù)階）、O(logn)（對(duì)數(shù)階）、O(n)（線性階）、O(nlogn)（線性對(duì)數(shù)階）、O(n^2)（平方階）、O(n^3)（立方階）
非多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長(zhǎng)，算法的執(zhí)行時(shí)間和空間占用暴增，這類(lèi)算法性能極差。包括， O(2^n)（指數(shù)階）、O(n!)（階乘階）
五、如何掌握好復(fù)雜度分析方法？復(fù)雜度分析關(guān)鍵在于多練，所謂孰能生巧。
六、最好、最壞、平均、均攤時(shí)間復(fù)雜度一、概念：1.最壞情況時(shí)間復(fù)雜度：代碼在最理想情況下執(zhí)行的時(shí)間復(fù)雜度。
2.最好情況時(shí)間復(fù)雜度：代碼在最壞情況下執(zhí)行的時(shí)間復(fù)雜度。
3.平均時(shí)間復(fù)雜度：用代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值表示。
4.均攤時(shí)間復(fù)雜度：在代碼執(zhí)行的所有復(fù)雜度情況中絕大部分是低級(jí)別的復(fù)雜度，個(gè)別情況是高級(jí)別復(fù)雜度且發(fā)生具有時(shí)序關(guān)系時(shí)，可以將個(gè)別高級(jí)別復(fù)雜度均攤到低級(jí)別復(fù)雜度上?；旧暇鶖偨Y(jié)果就等于低級(jí)別復(fù)雜度。
1.同一段代碼在不同情況下時(shí)間復(fù)雜度會(huì)出現(xiàn)量級(jí)差異，為了更全面，更準(zhǔn)確的描述代碼的時(shí)間復(fù)雜度，所以引入這4個(gè)概念。
2.代碼復(fù)雜度在不同情況下出現(xiàn)量級(jí)差別時(shí)才需要區(qū)別這四種復(fù)雜度。大多數(shù)情況下，是不需要區(qū)別分析它們的。
1.平均時(shí)間復(fù)雜度
代碼在不同情況下復(fù)雜度出現(xiàn)量級(jí)差別，則用代碼所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值表示。
2.均攤時(shí)間復(fù)雜度
兩個(gè)條件滿足時(shí)使用：1）代碼在絕大多數(shù)情況下是低級(jí)別復(fù)雜度，只有極少數(shù)情況是高級(jí)別復(fù)雜度；2）低級(jí)別和高級(jí)別復(fù)雜度出現(xiàn)具有時(shí)序規(guī)律。均攤結(jié)果一般都等于低級(jí)別復(fù)雜度。
我不認(rèn)為是多此一舉，漸進(jìn)時(shí)間，空間復(fù)雜度分析為我們提供了一個(gè)很好的理論分析的方向，并且它是宿主平臺(tái)無(wú)關(guān)的，能夠讓我們對(duì)我們的程序或算法有一個(gè)大致的認(rèn)識(shí)，讓我們知道，比如在最壞的情況下程序的執(zhí)行效率如何，同時(shí)也為我們交流提供了一個(gè)不錯(cuò)的橋梁，我們可以說(shuō)，算法1的時(shí)間復(fù)雜度是O(n)，算法2的時(shí)間復(fù)雜度是O(logN)，這樣我們立刻就對(duì)不同的算法有了一個(gè)“效率”上的感性認(rèn)識(shí)。
當(dāng)然，漸進(jìn)式時(shí)間，空間復(fù)雜度分析只是一個(gè)理論模型，只能提供給粗略的估計(jì)分析，我們不能直接斷定就覺(jué)得O(logN)的算法一定優(yōu)于O(n), 針對(duì)不同的宿主環(huán)境，不同的數(shù)據(jù)集，不同的數(shù)據(jù)量的大小，在實(shí)際應(yīng)用上面可能真正的性能會(huì)不同，個(gè)人覺(jué)得，針對(duì)不同的實(shí)際情況，進(jìn)而進(jìn)行一定的性能基準(zhǔn)測(cè)試是很有必要的，比如在統(tǒng)一一批手機(jī)上(同樣的硬件，系統(tǒng)等等)進(jìn)行橫向基準(zhǔn)測(cè)試，進(jìn)而選擇適合特定應(yīng)用場(chǎng)景下的最有算法。
綜上所述，漸進(jìn)式時(shí)間，空間復(fù)雜度分析與性能基準(zhǔn)測(cè)試并不沖突，而是相輔相成的，但是一個(gè)低階的時(shí)間復(fù)雜度程序有極大的可能性會(huì)優(yōu)于一個(gè)高階的時(shí)間復(fù)雜度程序，所以在實(shí)際編程中，時(shí)刻關(guān)心理論時(shí)間，空間度模型是有助于產(chǎn)出效率高的程序的，同時(shí)，因?yàn)闈u進(jìn)式時(shí)間，空間復(fù)雜度分析只是提供一個(gè)粗略的分析模型，因此也不會(huì)浪費(fèi)太多時(shí)間，重點(diǎn)在于在編程時(shí)，要具有這種復(fù)雜度分析的思維。
歡迎大家關(guān)注公眾號(hào)，不定時(shí)干貨，只做有價(jià)值的輸出
作者：Dawnzhang
出處：https://www.cnblogs.com/clwydjgs/p/9718754.html
版權(quán)：本文版權(quán)歸作者
轉(zhuǎn)載：歡迎轉(zhuǎn)載，但未經(jīng)作者同意，必須保留此段聲明；必須在文章中給出原文連接；否則必究法律責(zé)任
當(dāng)前文章：數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之復(fù)雜度分析-創(chuàng)新互聯(lián)
分享地址：http://m.jiaotiyi.com/article/hooce.html