一、定義

時(shí)間和空間是程序的一個(gè)硬性指標(biāo)，一個(gè)用來(lái)衡量 代碼執(zhí)行的速度 ，一個(gè)用來(lái)衡量 存儲(chǔ)空間的大小

程序 = ?數(shù)據(jù)結(jié)構(gòu) + 算法

• 時(shí)間復(fù)雜度：就是執(zhí)行程序的快慢，速度越快，時(shí)間復(fù)雜度就越好。
• 空間復(fù)雜度：就是執(zhí)行程序需要的存儲(chǔ)空間的大小，執(zhí)行程序需要的存儲(chǔ)空間越小就越好。

二、時(shí)間復(fù)雜度的計(jì)算

表示方法

我們一般用 大O符號(hào)表示法來(lái)表示時(shí)間復(fù)雜度：T(n) = O(f(n)) n是影響復(fù)雜度變化的因子，f(n)是復(fù)雜度具體的算法。

常見(jiàn)的時(shí)間復(fù)雜度量級(jí)

• 常數(shù)階O(1)
• 線性階O(n)
• 對(duì)數(shù)階O(logN)
• 線性對(duì)數(shù)階O(nlogN)
• 平方階O(n2)
• 立方階O(n3)
• K次方階O(n^k)
• 指數(shù)階(2^n)

接下來(lái)再看一下不同的復(fù)雜度所對(duì)應(yīng)的算法類型。

常數(shù)階O(1)

int?a?=?1;
int?b?=?2;
int?c?=?3;
123

我們假定每執(zhí)行一行代碼所需要消耗的時(shí)間為1個(gè)時(shí)間單位，那么以上3行代碼就消耗了3個(gè)時(shí)間單位。那是不是這段代碼的時(shí)間復(fù)雜度表示為O(n)呢 ？其實(shí)不是的，因?yàn)榇驩符號(hào)表示法并不是用于來(lái)真實(shí)代表算法的執(zhí)行時(shí)間的，它是用來(lái)表示代碼執(zhí)行時(shí)間的增長(zhǎng)變化趨勢(shì)的。上面的算法并沒(méi)有隨著某個(gè)變量的增長(zhǎng)而增長(zhǎng)，那么無(wú)論這類代碼有多長(zhǎng)，即使有幾萬(wàn)幾十萬(wàn)行，都可以用O(1)來(lái)表示它的時(shí)間復(fù)雜度。

線性階O(n)

for(i?=?1;?i?<=?n;?i++)?{
???j?=?i;
???j++;
}
1234

看這段代碼會(huì)執(zhí)行多少次呢？第1行會(huì)執(zhí)行1次，第2行和第3行會(huì)分別執(zhí)行n次，總的執(zhí)行時(shí)間也就是 2n + 1 次，那它的時(shí)間復(fù)雜度表示是 O(2n + 1) 嗎？No ! 還是那句話：“大O符號(hào)表示法并不是用于來(lái)真實(shí)代表算法的執(zhí)行時(shí)間的，它是用來(lái)表示代碼執(zhí)行時(shí)間的增長(zhǎng)變化趨勢(shì)的”。所以它的時(shí)間復(fù)雜度其實(shí)是O(n);

對(duì)數(shù)階O(logN)

int?i?=?1;
while(i?????i?=?i?*?2;
}
1234

可以看到每次循環(huán)的時(shí)候 i 都會(huì)乘2，那么總共循環(huán)的次數(shù)就是log2n，因此這個(gè)代碼的時(shí)間復(fù)雜度為O(logn)。這兒有個(gè)問(wèn)題，為什么明明應(yīng)該是O(log2n）,卻要寫成O(logn)呢？其實(shí)這里的底數(shù)對(duì)于研究程序運(yùn)行效率不重要，寫代碼時(shí)要考慮的是數(shù)據(jù)規(guī)模n對(duì)程序運(yùn)行效率的影響，常數(shù)部分則忽略，同樣的，如果不同時(shí)間復(fù)雜度的倍數(shù)關(guān)系為常數(shù)，那也可以近似認(rèn)為兩者為同一量級(jí)的時(shí)間復(fù)雜度。

線性對(duì)數(shù)階O(nlogN)

for(m?=?1;?m?????i?=?1;
????while(i?????????i?=?i?*?2;
????}
}
123456

線性對(duì)數(shù)階O(nlogN) 其實(shí)非常容易理解，將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話，那么它的時(shí)間復(fù)雜度就是 n * O(logN)，也就是了O(nlogN)。

平方階O(n2)

for(x?=?1;?i?<=?n;?x++){
???for(i?=?1;?i?<=?n;?i++)?{
???????j?=?i;
???????j++;
????}
}
123456

把 O(n) 的代碼再嵌套循環(huán)一遍，它的時(shí)間復(fù)雜度就是 O(n2) 了。

立方階O(n3)、K次方階O(n^k)

參考上面的O(n2) 去理解就好了，O(n3)相當(dāng)于三層n循環(huán)，其它的類似。

三、空間復(fù)雜度計(jì)算

空間復(fù)雜度 O(1)

如果算法執(zhí)行所需要的臨時(shí)空間不隨著某個(gè)變量n的大小而變化，即此算法空間復(fù)雜度為一個(gè)常量，可表示為 O(1)。

int?i?=?1;
int?j?=?2;
++i;
j++;
int?m?=?i?+?j;
12345

代碼中的 i、j、m 所分配的空間都不隨著處理數(shù)據(jù)量變化，因此它的空間復(fù)雜度 S(n) = O(1)。

空間復(fù)雜度 O(n)

int[]?m?=?new?int[n]
for(i?=?1;?i?<=?n;?++i)?{
???j?=?i;
???j++;
}
12345

這段代碼中，第一行new了一個(gè)數(shù)組出來(lái)，這個(gè)數(shù)據(jù)占用的大小為n，后面雖然有循環(huán)，但沒(méi)有再分配新的空間，因此，這段代碼的空間復(fù)雜度主要看第一行即可，即 S(n) = O(n)。

總結(jié)

評(píng)價(jià)一個(gè)算法的效率主要是看它的時(shí)間復(fù)雜度和空間復(fù)雜度情況?？赡苡械拈_(kāi)發(fā)者接觸時(shí)間復(fù)雜度和空間復(fù)雜度的優(yōu)化不太多（尤其是客戶端），但在服務(wù)端的應(yīng)用是比較廣泛的，在巨大并發(fā)量的情況下，小部分時(shí)間復(fù)雜度或空間復(fù)雜度上的優(yōu)化都能帶來(lái)巨大的性能提升，是非常有必要了解的。

大家好，下面是我的另一個(gè)號(hào)，會(huì)發(fā)一些比較私密的內(nèi)容，歡迎大家關(guān)注！