前言

小A和小B兩人寫了相同一個功能代碼，而小A的代碼老板運(yùn)行后發(fā)現(xiàn)耗時(shí)為100ms，消耗內(nèi)存10MB。而小B的代碼老板運(yùn)行以后，發(fā)現(xiàn)耗時(shí)為100S，消耗內(nèi)存100MB。如果你是老板你會選則使用誰的代碼。對于超過3秒即劃走的用戶而言，100s顯然是不行的。小A和小B代碼耗時(shí)與運(yùn)行時(shí)占用內(nèi)存的2種方式，是判斷算法好壞的最重要的2種標(biāo)準(zhǔn)，分別為時(shí)間復(fù)雜度與空間復(fù)雜度。上面都是程序運(yùn)行以后才知道耗時(shí)與占用內(nèi)存，那么如何在沒有運(yùn)行程序時(shí)對算法進(jìn)行提前預(yù)估呢？

關(guān)鍵代碼執(zhí)行次數(shù)

要預(yù)估時(shí)間復(fù)雜度，可以計(jì)算算法中關(guān)鍵代碼的操作執(zhí)行次數(shù)。

如下

情景一：

小明在繞操場勻速跑步2秒跑完1米，跑300米則需要600秒，如果跑步n米，則需要2 n 秒。則有

T(n) = 2n

情景二：

小明繞操場跑步，跑第1米需要1秒，跑第2米需要2秒，跑第3米需要3秒...跑n米需要n秒。

則小明跑n米的函數(shù)計(jì)算公式為

T(n) = 1 + 2 + 3+ 4 + ... + n
= (1 + n)n/2
=0.5n + 0.5n^2

情景三

小明繞操場跑步，總路程40米，第1秒能跑27米，跑第2秒能跑9米，第3秒能跑3米，跑完最后一米需要多長時(shí)間。由對數(shù)運(yùn)算公式可得，小明跑完40米的計(jì)算公式為

T(n) = log(3)(40)

若總路程為n 米，則有

T(n) = log(3)(n)

漸進(jìn)時(shí)間復(fù)雜度

通過情景一二的計(jì)算，我們可以預(yù)估一個算法的時(shí)間復(fù)雜度，但因?yàn)楫?dāng)n取值不一樣時(shí)，仍然不能判斷到底哪一個更快，例如當(dāng)n為1時(shí)，明顯情景二更快一些。這時(shí)我們需要使用漸進(jìn)時(shí)間復(fù)雜度進(jìn)行分析，即大O表示法。

當(dāng)n趨近于無限大時(shí)，有 T(n) / f(n) 的極限值有不為0的常數(shù)，則記作T(n) = O(f(n))。

情景一通過大O表示法則為：O(2n)，由于n趨近于無限大，忽略常數(shù)項(xiàng)，則記作O(n)
情景二通過大O表示法則為：O(0.5n + 0.5n^2 )，由于n趨近于無限大，忽略常數(shù)項(xiàng)保留最高階項(xiàng)，記作O(n^2)。
情景三通過大O表示法則為：O(log(3)(n))，由于為了與冪次方做對比，則通過換底公式有，O(log(2)(n) / log(2)(3))，由于n趨近于無限大忽略除數(shù)，底數(shù)足夠小省略底數(shù)不寫，則有O(log n)
情景四冪函數(shù)，同樣通過換底公式則有 O(2^x)

通過下圖，我們分析出當(dāng)n無限大時(shí)，常用的幾個函數(shù)耗時(shí)從小到大為：

由于對數(shù)函數(shù)畫圖時(shí)沒找到2為底在哪設(shè)置，hhhh

O(1) < O(log n) < O(n^2) < O(2^n)

空間復(fù)雜度

在程序運(yùn)行指令中，需要存儲一些中間數(shù)據(jù)所占用的內(nèi)存空間即為空間復(fù)雜度，有 S(n) = O(f(n))。

如下函數(shù)，傳入的n并不影響i所占用的空間，記作O(1)

f(n) {
  let i = 3n
}

如下函數(shù)，傳入的n所占用總空間成正比，記作O(n)

f(n) {
  let array = new Array(n)
}

如下函數(shù)，傳入的n與二位數(shù)組成正比，記作O(n^2)

f(n) {
  let array = new Array(n).fill(new Array(n))
}

取舍

計(jì)算機(jī)的運(yùn)行速度和空間資源是有限的，時(shí)間復(fù)雜度與空間復(fù)雜度當(dāng)然都越小越好。在絕大多數(shù)情況下時(shí)間復(fù)雜度更為重要一些，我們寧可多分配一些內(nèi)存空間，也要提升程序的運(yùn)行速度。