復(fù)雜度分析總結(jié)

一猎贴、什么是復(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)鍵在于多練辅柴,所謂孰能生巧。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末瞭吃,一起剝皮案震驚了整個濱河市碌嘀,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌歪架,老刑警劉巖股冗,帶你破解...
    沈念sama閱讀 212,657評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異和蚪,居然都是意外死亡止状,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,662評論 3 385
  • 文/潘曉璐 我一進店門惠呼,熙熙樓的掌柜王于貴愁眉苦臉地迎上來导俘,“玉大人,你說我怎么就攤上這事剔蹋÷帽。” “怎么了?”我有些...
    開封第一講書人閱讀 158,143評論 0 348
  • 文/不壞的土叔 我叫張陵泣崩,是天一觀的道長少梁。 經(jīng)常有香客問我,道長矫付,這世上最難降的妖魔是什么凯沪? 我笑而不...
    開封第一講書人閱讀 56,732評論 1 284
  • 正文 為了忘掉前任,我火速辦了婚禮买优,結(jié)果婚禮上妨马,老公的妹妹穿的比我還像新娘。我一直安慰自己杀赢,他們只是感情好烘跺,可當我...
    茶點故事閱讀 65,837評論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著脂崔,像睡著了一般滤淳。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上砌左,一...
    開封第一講書人閱讀 50,036評論 1 291
  • 那天脖咐,我揣著相機與錄音铺敌,去河邊找鬼。 笑死屁擅,一個胖子當著我的面吹牛偿凭,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播煤蹭,決...
    沈念sama閱讀 39,126評論 3 410
  • 文/蒼蘭香墨 我猛地睜開眼笔喉,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了硝皂?” 一聲冷哼從身側(cè)響起常挚,我...
    開封第一講書人閱讀 37,868評論 0 268
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎稽物,沒想到半個月后奄毡,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,315評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡贝或,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,641評論 2 327
  • 正文 我和宋清朗相戀三年吼过,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片咪奖。...
    茶點故事閱讀 38,773評論 1 341
  • 序言:一個原本活蹦亂跳的男人離奇死亡盗忱,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出羊赵,到底是詐尸還是另有隱情趟佃,我是刑警寧澤,帶...
    沈念sama閱讀 34,470評論 4 333
  • 正文 年R本政府宣布昧捷,位于F島的核電站闲昭,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏靡挥。R本人自食惡果不足惜序矩,卻給世界環(huán)境...
    茶點故事閱讀 40,126評論 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望跋破。 院中可真熱鬧簸淀,春花似錦、人聲如沸毒返。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,859評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽饿悬。三九已至,卻和暖如春聚霜,著一層夾襖步出監(jiān)牢的瞬間狡恬,已是汗流浹背珠叔。 一陣腳步聲響...
    開封第一講書人閱讀 32,095評論 1 267
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留弟劲,地道東北人祷安。 一個月前我還...
    沈念sama閱讀 46,584評論 2 362
  • 正文 我出身青樓,卻偏偏與公主長得像兔乞,于是被迫代替她去往敵國和親汇鞭。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 43,676評論 2 351

推薦閱讀更多精彩內(nèi)容