一裸违、什么是復(fù)雜度分析?
- 數(shù)據(jù)結(jié)構(gòu)和算法解決是“如何讓計(jì)算機(jī)更快時(shí)間千扶、更省空間的解決問題”勉抓。
- 因此需從執(zhí)行時(shí)間和占用空間兩個(gè)維度來評(píng)估數(shù)據(jù)結(jié)構(gòu)和算法的性能骇吭。
- 分別用時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)概念來描述性能問題吨述，二者統(tǒng)稱為復(fù)雜度岩睁。
- 復(fù)雜度描述的是算法執(zhí)行時(shí)間(或占用空間)與數(shù)據(jù)規(guī)模的增長(zhǎng)關(guān)系。
二揣云、為什么要進(jìn)行復(fù)雜度分析?
- 和性能測(cè)試相比捕儒，復(fù)雜度分析有不依賴執(zhí)行環(huán)境、成本低、效率高刘莹、易操作阎毅、指導(dǎo)性強(qiáng)的特點(diǎn)。
- 掌握復(fù)雜度分析点弯，將能編寫出性能更優(yōu)的代碼扇调，有利于降低系統(tǒng)開發(fā)和維護(hù)成本。
三抢肛、如何進(jìn)行復(fù)雜度分析?
- 大O表示法
1)來源
算法的執(zhí)行時(shí)間與每行代碼的執(zhí)行次數(shù)成正比肃拜，用T(n) = O(f(n))表示，其中T(n)表示算法執(zhí)行總時(shí)
間雌团，f(n)表示每行代碼執(zhí)行總次數(shù)燃领，而n往往表示數(shù)據(jù)的規(guī)模。
2)特點(diǎn)
以時(shí)間復(fù)雜度為例锦援，由于時(shí)間復(fù)雜度描述的是算法執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模的增長(zhǎng)變化趨勢(shì)猛蔽，所以常量
階、低階以及系數(shù)實(shí)際上對(duì)這種增長(zhǎng)趨勢(shì)不產(chǎn)決定性影響灵寺，所以在做時(shí)間復(fù)雜度分析時(shí)忽略這些項(xiàng)曼库。 - 復(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í)間和空間占用暴增汇陆，這類算法性能極差。包括恩敌，O(2^n)(指數(shù)階)瞬测、O(n!)(階乘階)
五、如何掌握好復(fù)雜度分析方法?
復(fù)雜度分析關(guān)鍵在于多練，所謂孰能生巧月趟。
