數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之復(fù)雜度分析-創(chuàng)新互聯(lián)

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之 復(fù)雜度分析

創(chuàng)新互聯(lián)建站主營思明網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,重慶APP開發(fā),思明h5小程序制作搭建,思明網(wǎng)站營銷推廣歡迎思明等地區(qū)企業(yè)咨詢前言：

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

正文：復(fù)雜度分析 一、什么是復(fù)雜度分析？

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

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

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

二、為什么要進(jìn)行復(fù)雜度分析？

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

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

三、如何進(jìn)行復(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 時間復(fù)雜度并不具體表示代碼真正的執(zhí)行時間，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，也叫作漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度，

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

2.復(fù)雜度分析法則

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

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

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

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

四、常用的復(fù)雜度級別？

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

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

五、如何掌握好復(fù)雜度分析方法？

復(fù)雜度分析關(guān)鍵在于多練，所謂孰能生巧。

六、最好、最壞、平均、均攤時間復(fù)雜度一、概念：

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

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

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

三、如何分析平均、均攤時間復(fù)雜度？

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

 有人說，我們項(xiàng)目之前都會進(jìn)行性能測試，再做代碼的時間復(fù)雜度、空間復(fù)雜度分析，是不是多此一舉呢？每段代碼都分析一下時間復(fù)雜度、空間復(fù)雜度，是不是很浪費(fèi)時間呢？

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

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

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

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

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

網(wǎng)站欄目：數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之復(fù)雜度分析-創(chuàng)新互聯(lián)
文章URL：http://muchs.cn/article24/hooce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、網(wǎng)站設(shè)計(jì)、Google、企業(yè)網(wǎng)站制作、關(guān)鍵詞優(yōu)化、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)