一猎贴、什么是復(fù)雜度分析?
1.數(shù)據(jù)結(jié)構(gòu)和算法解決是“如何讓計算機更快時間终佛、更省空間的解決問題”安接。
2.因此需從執(zhí)行時間和占用空間兩個維度來評估數(shù)據(jù)結(jié)構(gòu)和算法的性能翔忽。
3.分別用時間復(fù)雜度和空間復(fù)雜度兩個概念來描述性能問題,二者統(tǒng)稱為復(fù)雜度盏檐。
4.復(fù)雜度描述的是算法執(zhí)行時間(或占用空間)與數(shù)據(jù)規(guī)模的增長關(guān)系歇式。
二、為什么要進行復(fù)雜度分析胡野?
1.和性能測試相比材失,復(fù)雜度分析有不依賴執(zhí)行環(huán)境、成本低给涕、效率高豺憔、易操作额获、指導(dǎo)性強的特點。
2.掌握復(fù)雜度分析恭应,將能編寫出性能更優(yōu)的代碼抄邀,有利于降低系統(tǒng)開發(fā)和維護成本。
三昼榛、如何進行復(fù)雜度分析境肾?
1.大O表示法
1)來源
算法的執(zhí)行時間與每行代碼的執(zhí)行次數(shù)成正比,用T(n) = O(f(n))表示胆屿,其中T(n)表示算法執(zhí)行總時間奥喻,f(n)表示每行代碼執(zhí)行總次數(shù),而n往往表示數(shù)據(jù)的規(guī)
模非迹。
2)特點
03|復(fù)雜度分析(上):如何分析环鲤、統(tǒng)計算法的執(zhí)行效率和資源消耗?
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/03復(fù)雜度分析(上):如何分析憎兽、統(tǒng)計算法的執(zhí)行效率和資源消耗冷离?.html[2019/1/15 15:35:11]
以時間復(fù)雜度為例,由于時間復(fù)雜度描述的是算法執(zhí)行時間與數(shù)據(jù)規(guī)模的增長變化趨勢纯命,所以常量階西剥、低階以及系數(shù)實際上對這種增長趨勢不產(chǎn)決定性影響
,所以在做時間復(fù)雜度分析時忽略這些項亿汞。
2.復(fù)雜度分析法則
1)單段代碼看高頻:比如循環(huán)瞭空。
2)多段代碼取最大:比如一段代碼中有單循環(huán)和多重循環(huán),那么取多重循環(huán)的復(fù)雜度疗我。
3)嵌套代碼求乘積:比如遞歸咆畏、多重循環(huán)等
4)多個規(guī)模求加法:比如方法有兩個參數(shù)控制兩個循環(huán)的次數(shù),那么這時就取二者復(fù)雜度相加吴裤。
四鳖眼、常用的復(fù)雜度級別?
多項式階:隨著數(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!)(階乘階)
五、如何掌握好復(fù)雜度分析方法矗烛?
復(fù)雜度分析關(guān)鍵在于多練辅柴,所謂孰能生巧。