時(shí)間復(fù)雜度

什么是時(shí)間復(fù)雜度

在計(jì)算機(jī)科學(xué)中买优,算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)末捣,它定量描述了該算法的運(yùn)行時(shí)間。時(shí)間復(fù)雜度常用大O符號(hào)表述篷就,不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。

T(n)=O(f(n))

一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度近忙。T(n)表示算法中的語(yǔ)句執(zhí)行次數(shù)竭业,‘;’代表一個(gè)語(yǔ)句結(jié)束及舍。

忽略掉T(n)中的常量未辆、低次冪和最高次冪的系數(shù),則為f(n)

當(dāng)n趨近于無(wú)窮大時(shí)锯玛,T(n)/f(n)的極限值為不等于零的常數(shù)咐柜,則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n)),稱(chēng)O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度攘残,簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度拙友。

我們常常看到別人描述說(shuō)歼郭,冒泡算法的時(shí)間復(fù)雜度是O(n2)遗契,那么O(n2)是怎么的出來(lái)的呢?

怎么計(jì)算時(shí)間復(fù)雜度

我們就用冒泡排序算法作為例子病曾,來(lái)計(jì)算下時(shí)間復(fù)雜度

function bubbleSort(arr) {    
    var i=arr.length, j;                             
    var tempExchangVal;                           
    while (i > 0) {                              
      for (j = 0; j < i - 1; j++) {          
          if (arr[j] > arr[j + 1]) {                
           tempExchangVal = arr[j]; 
             arr[j] = arr[j + 1]; 
             arr[j + 1] = tempExchangVal; 
         }
        }
        i--;
    }
    return arr;
}
語(yǔ)句 執(zhí)行次數(shù)
var i, j; 1
var tempExchangVal; 1
i > 0 n
j = 0; n
j < i - 1; j++ n(n-1)/2
arr[j] > arr[j + 1] n(n-1)/2
tempExchangVal = arr[j]; n(n-1)/2
arr[j] = arr[j + 1]; n(n-1)/2
arr[j + 1] = tempExchangVal; n(n-1)/2

所以這個(gè)算法總共執(zhí)行了2+2n+5n(n-1)/2次

T(n) = 2+2n+5n(n-1)/2牍蜂;
忽略掉T(n)中的常量、低次冪和最高次冪的系數(shù)泰涂,則為f(n)
f(n) = n^2

T(n)/f(n) = (2- 3n + 5/2 n^2 ) / n^2
當(dāng)n趨向無(wú)窮大時(shí)鲫竞,T(n) / f(n)是5/2,為不等于零的常數(shù)负敏,則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)贡茅。
T(n)=O(f(n))
所以時(shí)間復(fù)雜度為O(f(n)) = O(n^2 )

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子顶考,更是在濱河造成了極大的恐慌赁还,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件驹沿,死亡現(xiàn)場(chǎng)離奇詭異艘策,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)渊季,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)朋蔫,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人却汉,你說(shuō)我怎么就攤上這事驯妄。” “怎么了合砂?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵青扔,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我翩伪,道長(zhǎng)微猖,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任缘屹,我火速辦了婚禮凛剥,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘轻姿。我一直安慰自己犁珠,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布互亮。 她就那樣靜靜地躺著盲憎,像睡著了一般。 火紅的嫁衣襯著肌膚如雪胳挎。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,713評(píng)論 1 312
  • 那天溺森,我揣著相機(jī)與錄音慕爬,去河邊找鬼。 笑死屏积,一個(gè)胖子當(dāng)著我的面吹牛医窿,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播炊林,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼姥卢,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起独榴,我...
    開(kāi)封第一講書(shū)人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤僧叉,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后棺榔,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體瓶堕,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年症歇,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了郎笆。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡忘晤,死狀恐怖宛蚓,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情设塔,我是刑警寧澤凄吏,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站壹置,受9級(jí)特大地震影響竞思,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜钞护,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一盖喷、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧难咕,春花似錦课梳、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至爆土,卻和暖如春椭懊,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背步势。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工氧猬, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人坏瘩。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓盅抚,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親倔矾。 傳聞我的和親對(duì)象是個(gè)殘疾皇子妄均,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

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

  • 算法復(fù)雜度 時(shí)間復(fù)雜度 空間復(fù)雜度 什么是時(shí)間復(fù)雜度 算法執(zhí)行時(shí)間需通過(guò)依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗...
    KODIE閱讀 3,270評(píng)論 0 9
  • 算法的時(shí)間復(fù)雜度和空間復(fù)雜度-總結(jié)通常柱锹,對(duì)于一個(gè)給定的算法,我們要做 兩項(xiàng)分析丰包。第一是從數(shù)學(xué)上證明算法的正確性禁熏,這...
    Explorer_Mi閱讀 1,449評(píng)論 0 1
  • 通常,對(duì)于一個(gè)給定的算法烫沙,我們要做 兩項(xiàng)分析匹层。第一是從數(shù)學(xué)上證明算法的正確性,這一步主要用到形式化證明的方法及相關(guān)...
    西域小碼閱讀 1,871評(píng)論 0 11
  • 0锌蓄,時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量 1升筏,在計(jì)算時(shí)間復(fù)雜度的時(shí)候,先找出算法的基本操作瘸爽,然后根據(jù)相應(yīng)的各語(yǔ)...
    Santiagogogo閱讀 875評(píng)論 0 4
  • 1. 算法復(fù)雜度初認(rèn) 你循環(huán)的次數(shù)寫(xiě)成 n 的表達(dá)式您访,就是時(shí)間復(fù)雜度 你申請(qǐng)的變量數(shù)量寫(xiě)成 n 的表達(dá)式,就是空間...
    誰(shuí)動(dòng)了MyWorld閱讀 4,187評(píng)論 0 11