前言
小A和小B兩人寫了相同一個(gè)功能代碼，而小A的代碼老板運(yùn)行后發(fā)現(xiàn)耗時(shí)為100ms，消耗內(nèi)存10MB沪摄。而小B的代碼老板運(yùn)行以后，發(fā)現(xiàn)耗時(shí)為100S纱烘，消耗內(nèi)存100MB杨拐。如果你是老板你會(huì)選則使用誰(shuí)的代碼。對(duì)于超過(guò)3秒即劃走的用戶而言擂啥，100s顯然是不行的哄陶。小A和小B代碼耗時(shí)與運(yùn)行時(shí)占用內(nèi)存的2種方式，是判斷算法好壞的最重要的2種標(biāo)準(zhǔn)哺壶，分別為時(shí)間復(fù)雜度與空間復(fù)雜度屋吨。上面都是程序運(yùn)行以后才知道耗時(shí)與占用內(nèi)存，那么如何在沒(méi)有運(yùn)行程序時(shí)對(duì)算法進(jìn)行提前預(yù)估呢山宾？
關(guān)鍵代碼執(zhí)行次數(shù)
要預(yù)估時(shí)間復(fù)雜度至扰，可以計(jì)算算法中關(guān)鍵代碼的操作執(zhí)行次數(shù)。
如下
情景一：
小明在繞操場(chǎng)勻速跑步2秒跑完1米资锰，跑300米則需要600秒敢课，如果跑步n米，則需要2 n 秒。則有
T(n) = 2n
情景二：
小明繞操場(chǎng)跑步直秆，跑第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
情景三
小明繞操場(chǎng)跑步萨咳，總路程40米，第1秒能跑27米疫稿，跑第2秒能跑9米培他，第3秒能跑3米，跑完最后一米需要多長(zhǎng)時(shí)間遗座。由對(duì)數(shù)運(yùn)算公式可得舀凛，小明跑完40米的計(jì)算公式為
T(n) = log(3)(40)
若總路程為n 米，則有
T(n) = log(3)(n)
漸進(jìn)時(shí)間復(fù)雜度
通過(guò)情景一二的計(jì)算途蒋，我們可以預(yù)估一個(gè)算法的時(shí)間復(fù)雜度猛遍，但因?yàn)楫?dāng)n取值不一樣時(shí)，仍然不能判斷到底哪一個(gè)更快号坡，例如當(dāng)n為1時(shí)懊烤，明顯情景二更快一些。這時(shí)我們需要使用漸進(jìn)時(shí)間復(fù)雜度進(jìn)行分析宽堆，即大O表示法腌紧。
當(dāng)n趨近于無(wú)限大時(shí)，有 T(n) / f(n) 的極限值有不為0的常數(shù)畜隶，則記作T(n) = O(f(n))壁肋。
情景一通過(guò)大O表示法則為：O(2n)，由于n趨近于無(wú)限大籽慢，忽略常數(shù)項(xiàng)浸遗，則記作O(n)
情景二通過(guò)大O表示法則為：O(0.5n + 0.5n^2 )，由于n趨近于無(wú)限大箱亿，忽略常數(shù)項(xiàng)保留最高階項(xiàng)跛锌，記作O(n^2)。
情景三通過(guò)大O表示法則為：O(log(3)(n))极景，由于為了與冪次方做對(duì)比察净，則通過(guò)換底公式有驾茴，O(log(2)(n) / log(2)(3))盼樟，由于n趨近于無(wú)限大忽略除數(shù)，底數(shù)足夠小省略底數(shù)不寫锈至，則有O(log n)
情景四冪函數(shù)晨缴，同樣通過(guò)換底公式則有 O(2^x)
通過(guò)下圖，我們分析出當(dāng)n無(wú)限大時(shí)峡捡，常用的幾個(gè)函數(shù)耗時(shí)從小到大為：
由于對(duì)數(shù)函數(shù)畫圖時(shí)沒(méi)找到2為底在哪設(shè)置击碗，hhhh
O(1) < O(log n) < O(n^2) < O(2^n)
空間復(fù)雜度
在程序運(yùn)行指令中筑悴，需要存儲(chǔ)一些中間數(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)行速度。
