新的一年邑雅，先給大家整理分享一個簡單而又重要的知識點：時間復(fù)雜度和空間復(fù)雜度坑质。因為在前幾篇文章中，提到了時間復(fù)雜度前硫，也許有些小伙伴還不清楚胞得。
先給大家出個思考題，計算：sum = 1+2+3+...+n 屹电，計算 sum 的值阶剑。
為什么需要復(fù)雜度分析
- 學習數(shù)據(jù)和算法就是為了解“快”和“省”的問題，也就是如何設(shè)計你的代碼才能使運算效率更快危号，占用空間更小牧愁。那如何來計算代碼執(zhí)行效率呢？這里就會用到復(fù)雜度分析外莲。
- 雖然我們可以用代碼準確的計算出執(zhí)行時間猪半，但是這也會有很多局限性。
- 數(shù)據(jù)規(guī)模的不同會直接影響到測試結(jié)果偷线。比如說同一個排序算法磨确，排序順序不一樣，那么最后的計算效率的結(jié)果也會不一樣声邦；如果恰好已經(jīng)是排序好的了數(shù)組俐填，那么執(zhí)行時間就會更短。又比如說如果數(shù)據(jù)規(guī)模比較小的話翔忽，測試結(jié)果可能也無法反應(yīng)算法的性能英融。
- 測試的環(huán)境不同也會影響到測試結(jié)果盏檐。比如說同一套代碼分別在 i3 和 i7 處理器上進行測試，那么 i7 上的測試時間肯定會比 i3 上的短驶悟。
所以需要一個不用準確的測試結(jié)果來衡量胡野，就可以粗略地估計代碼執(zhí)行時間的方法。這就是復(fù)雜度分析痕鳍。
大 O 復(fù)雜度表示法
以一個例子開始硫豆，請估算下面代碼的執(zhí)行時間
function total(n) { // 1
var sum = 0; // 2
for (var i = 0; i < n; i++) { // 3
sum += i; // 4
} //5
} //6
我們假設(shè)每行代碼執(zhí)行的時間都一樣，記做 t笼呆，那么上面的函數(shù)中的第 2 行需要 1 個 t 的時間熊响，第 3 行 和 第 4 行分別需要 n 個 t 的時間，那么這段代碼總的執(zhí)行時間為 (2n+1)*t诗赌。
那么按照上面的分析方法汗茄，請估算下面代碼的執(zhí)行時間
function total(n) { // 1
var sum = 0; // 2
for (var i = 0; i < n; i++) { // 3
for (var j = 0; j < n; j++) { // 4
sum = sum + i + j; // 5
}
}
}
第 2 行需要一個 t 的時間，第 3 行需要 n 個 t 的時間铭若，第 4 行和第 5 行分別需要 n2 個的時間洪碳，那么這段代碼總的執(zhí)行時間為 (2n2+n+1)*t 的時間。
從數(shù)學角度來看叼屠，我們可以得出個規(guī)律：代碼的總執(zhí)行時間 T(n) 與每行代碼的執(zhí)行次數(shù)成正比
T(n) = O(f(n))
在這個公式中瞳腌，T(n) 表示代碼的執(zhí)行時間；n 表示數(shù)據(jù)規(guī)模的大芯涤辍嫂侍；f(n) 表示每行代碼執(zhí)行的次數(shù)總和；O 表示代碼的執(zhí)行時間 T(n) 與 f(n) 表達式成正比荚坞。
所以上邊兩個函數(shù)的執(zhí)行時間可以標記為 T(n) = O(2n+1) 和 T(n) = O(2n2+n+1)吵冒。這就是大 O 時間復(fù)雜度表示法，它不代表代碼真正的執(zhí)行時間西剥，而是表示代碼隨數(shù)據(jù)規(guī)模增長的變化趨勢痹栖，簡稱時間復(fù)雜度。
而且當 n 很大時瞭空，我們可以忽略常數(shù)項揪阿，只保留一個最大量級即可。所以上邊的代碼執(zhí)行時間可以簡單標記為 T(n) = O(n) 和 T(n) = O(n2)咆畏。
時間復(fù)雜度分析
那如何分析一段代碼的時間復(fù)雜度呢南捂，可以利用下面的幾個方法
1.只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
我們在分析一段代碼的時間復(fù)雜度時，我們只要關(guān)注循環(huán)次數(shù)最多的那一段代碼就 ok 了旧找。
比如說在第一段代碼中
function total(n) { // 1
var sum = 0; // 2
for (var i = 0; i < n; i++) { // 3
sum += i; // 4
} //5
} //6
只有第 3 行和第 4 行是執(zhí)行次數(shù)最多的溺健，分別執(zhí)行了 n 次，那么忽略常數(shù)項钮蛛，所以此段代碼的時間復(fù)雜度就是 O(n)鞭缭。
2.加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度剖膳。
比如說，看下面這段代碼的時間復(fù)雜度岭辣。
function total(n) {
// 第一個 for 循環(huán)
var sum1 = 0;
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
sum1 = sum1 + i + j;
}
}
// 第二個 for 循環(huán)
var sum2 = 0;
for(var i=0;i<1000;i++) {
sum2 = sum2 + i;
}
// 第三個 for 循環(huán)
var sum3 = 0;
for (var i = 0; i < n; i++) {
sum3 = sum3 + i;
}
}
我們先分別分析每段 for 循環(huán)的時間復(fù)雜度吱晒，再取他們中最大的量級來作為整段代碼的時間復(fù)雜度。
第一段 for 循環(huán)的時間復(fù)雜度為 O(n2)沦童。
第二段 for 循環(huán)執(zhí)行了 1000 次仑濒，是個常數(shù)量級，盡管對代碼的執(zhí)行時間會有影響偷遗，但是當 n 無限大的時候墩瞳，就可以忽略。因為它本身對增長趨勢沒有影響氏豌，所以這段代碼的時間復(fù)雜度可以忽略喉酌。
第三段 for 循環(huán)的時間復(fù)雜度為 O(n)。
總上箩溃，取最大量級，所以整段代碼的時間復(fù)雜度為 O(n2)碌嘀。
3.乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積涣旨。
比如說，看下面這段代碼的時間復(fù)雜度
function f(i) {
var sum = 0;
for (var j = 0; j < i; j++) {
sum += i;
}
return sum;
}
function total(n) {
var res = 0;
for (var i = 0; i < n; i++) {
res = res + f(i); // 調(diào)用 f 函數(shù)
}
}
單獨看 total 函數(shù)的時間復(fù)雜度就是為 T1(n)=O(n)股冗，但是考慮到 f 函數(shù)的時間復(fù)雜度也為 T2(n)=O(n)霹陡。
所以整段代碼的時間復(fù)雜度為 T(n) = T1(n) * T2(n) = O(n*n)=O(n2)。
幾種常見的時間復(fù)雜度分析
只看最高量級的復(fù)雜度
如上圖可以粗略的分為兩類止状，多項式量級和非多項式量級烹棉。其中，非多項式量級只有兩個：O(2n) 和 O(n!)
對應(yīng)的增長率如下圖所示
當數(shù)據(jù)規(guī)模 n 增長時怯疤，非多項式量級的執(zhí)行時間就會急劇增加浆洗，所以，非多項式量級的代碼算法是非常低效的算法集峦。
1. O(1)
O(1) 只是常量級時間復(fù)雜度表示法伏社，并不是代碼只有一行，比如說下面這段代碼
function total() {
var sum = 0;
for(var i=0;i<100;i++) {
sum += i;
}
}
雖然有這么多行塔淤，即使 for 循環(huán)執(zhí)行了 100 次摘昌，但是代碼的執(zhí)行時間不隨 n 的增大而增長，所以這樣的代碼復(fù)雜度就為 O(1)高蜂。
2. O(logn)聪黎、O(nlogn)
對數(shù)階時間復(fù)雜度的常見代碼如下
function total1(n) {
var sum = 0;
var i = 1;
while (i <= n) {
sum += i;
i = i * 2;
}
}
function total2(n) {
var sum = 0;
for (var i = 1; i <= n; i = i * 2) {
sum += i;
}
}
上面兩個函數(shù)都有一個相同點，變量 i 從 1 開始取值备恤，每循環(huán)一次乘以 2稿饰，當大于 n 時锦秒，循環(huán)結(jié)束。實際上湘纵，i 的取值就是一個等比數(shù)列脂崔，就像下面這樣
20 21 22 ... 2k... 2x =n;
所以只要知道 x 的值，就可以知道這兩個函數(shù)的執(zhí)行次數(shù)了梧喷。那由 2x = n 可以得出 x = log2n砌左，所以這兩個函數(shù)的時間復(fù)雜度為 O(log2n)。
再看下面兩個函數(shù)的時間復(fù)雜度
function total1(n) {
var sum = 0;
var i = 1;
while (i <= n) {
sum += i;
i = i * 3;
}
}
function total2(n) {
var sum = 0;
for (var i = 1; i <= n; i = i * 3) {
sum += i;
}
}
由上可以得知铺敌，這兩個函數(shù)的時間復(fù)雜度為 O(log3n) 汇歹。
由于我們可以忽略常數(shù)，也可以忽略對數(shù)中的底數(shù)偿凭，所以在對數(shù)階復(fù)雜度中产弹，統(tǒng)一表示為 O(logn)；那 O(nlogn) 的含義就很明確了弯囊，時間復(fù)雜度 為O(logn) 的代碼執(zhí)行了 n 次痰哨。
3. O(m+n)、O(m*n)
再來看一段特殊的代碼時間復(fù)雜度匾嘱，比如說
function total(m,n) {
var sum1 = 0;
for (var i = 0; i < n; i++) {
sum1 += i;
}
var sum2 = 0;
for (var i = 0; i < m; i++) {
sum2 += i;
}
return sum1 + sum2;
}
因為我們無法評估 m 和 n 誰的量級比較大斤斧，所以就不能忽略掉其中一個，這個函數(shù)的復(fù)雜度是有兩個數(shù)據(jù)的量級來決定的霎烙，所以此函數(shù)的時間復(fù)雜度為 O(m+n)撬讽；那么 O(m*n) 的時間復(fù)雜度類似。
空間復(fù)雜度分析
空間復(fù)雜度的話和時間復(fù)雜度類似推算即可悬垃。
所謂空間復(fù)雜度就是表示算法的存儲空間和數(shù)據(jù)規(guī)模之間的關(guān)系游昼。
比如說分析下面代碼的空間復(fù)雜度：
function initArr(n) {
var arr = [];
for (var i = 0; i < n; i++) {
arr[i] = i;
}
}
根據(jù)時間復(fù)雜度的推算，忽略掉常數(shù)量級尝蠕，每次數(shù)組賦值都會申請一個空間存儲變量烘豌，所以此函數(shù)的空間復(fù)雜度為 O(n)。
常見的空間復(fù)雜度只有 O(1)看彼、O(n)扇谣、O(n2)。其他的話很少會用到闲昭。
思考題解答
現(xiàn)在我們回到開始的思考題上罐寨，代碼實現(xiàn)很簡單：
function total(n) {
var sum = 0;
for (var i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
此函數(shù)的時間復(fù)雜度你現(xiàn)在應(yīng)該很容易就能看出來了，為 O(n)序矩。
我覺得這個時間復(fù)雜度有點高了鸯绿，我想要 O(1) 的時間復(fù)雜度函數(shù)來實現(xiàn)這個算法，可以嗎？
可以的瓶蝴，小數(shù)學神通高斯教會我們一招毒返，如下
function total(n) {
var sum = n*(n+1)/2
return sum;
}
此函數(shù)的時間復(fù)雜度僅僅為 O(1)，在數(shù)據(jù)規(guī)模比較龐大的時候舷手，下面的函數(shù)是不是明顯比上面的函數(shù)運算效率更高呢拧簸。
總結(jié)
復(fù)雜度也叫漸進復(fù)雜度，包括時間復(fù)雜度和空間復(fù)雜度男窟，一個表示執(zhí)行的快慢盆赤，一個表示內(nèi)存的消耗，用來分析算法執(zhí)行效率與數(shù)據(jù)規(guī)模之間的增長關(guān)系歉眷，可以粗略的表示牺六，越高階復(fù)雜度的算法，執(zhí)行效率越低汗捡。
學習了復(fù)雜度分析后淑际，是不是能避免寫出效率低的代碼呢？來給你的代碼做個分析吧扇住。
重點
如果有錯誤或者錯別字春缕，還請給我留言指出，謝謝艘蹋。
我們下期見锄贼。
