[[373785]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序新視界」，作者丑胖俠二師兄  。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序新視界公眾號(hào)。  

前言

算法(Algorithm)是指用來(lái)操作數(shù)據(jù)、解決程序問(wèn)題的一組方法。算法是大廠、外企面試的必備項(xiàng)，也是每個(gè)高級(jí)程序員的必備技能。針對(duì)同一問(wèn)題，可以有很多種算法來(lái)解決，但不同的算法在效率和占用存儲(chǔ)空間上的區(qū)別可能會(huì)很大。

那么，通過(guò)什么指標(biāo)來(lái)衡量算法的優(yōu)劣呢?其中，上面提到的效率可以用算法的時(shí)間復(fù)雜度來(lái)描述，而所占用的存儲(chǔ)空間可以用算法的空間復(fù)雜度來(lái)描述。

• 時(shí)間復(fù)雜度：用于評(píng)估執(zhí)行程序所消耗的時(shí)間，可以估算出程序?qū)μ幚砥鞯氖褂贸潭取?/li>
• 空間復(fù)雜度：用于評(píng)估執(zhí)行程序所占用的內(nèi)存空間，可以估算出程序?qū)τ?jì)算機(jī)內(nèi)存的使用程度。

在實(shí)踐中或面試中，我們不僅要能夠?qū)懗鼍唧w的算法來(lái)，還要了解算法的時(shí)間復(fù)雜度和空間復(fù)雜度，這樣才能夠評(píng)估出算法的優(yōu)劣。當(dāng)時(shí)間復(fù)雜度和空間復(fù)雜度無(wú)法同時(shí)滿足時(shí)，還需要從中選取一個(gè)平衡點(diǎn)。

一個(gè)算法通常存在最好、平均、最壞三種情況，我們一般關(guān)注的是最壞情況。最壞情況是算法運(yùn)行時(shí)間的上界，對(duì)于某些算法來(lái)說(shuō)，最壞情況出現(xiàn)的比較頻繁，也意味著平均情況和最壞情況一樣差。

通常，時(shí)間復(fù)雜度要比空間復(fù)雜度更容易出問(wèn)題，更多研究的是時(shí)間復(fù)雜度，面試中如果沒(méi)有特殊說(shuō)明，講的也是時(shí)間復(fù)雜度。

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

要獲得算法的時(shí)間復(fù)雜度，最直觀的想法是把算法程序運(yùn)行一遍，自然可以獲得。但實(shí)踐中往往受限于測(cè)試環(huán)境、數(shù)據(jù)規(guī)模等因素，直接測(cè)試算法要么難以實(shí)現(xiàn)，要么誤差較大，而且理論上也沒(méi)必要對(duì)每個(gè)算法都進(jìn)行一遍測(cè)試，只需要找到一種評(píng)估指標(biāo)，獲得算法執(zhí)行所消耗時(shí)間的基本趨勢(shì)即可。

時(shí)間頻度

通常，一個(gè)算法所花費(fèi)的時(shí)間與代碼語(yǔ)句執(zhí)行的次數(shù)成正比，算法執(zhí)行語(yǔ)句越多，消耗的時(shí)間也就越多。我們把一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為時(shí)間頻度，記作T(n)。

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

在時(shí)間頻度T(n)中，n代表著問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)，T(n)也會(huì)不斷地隨之變化。那么，如果我們想知道T(n)隨著n變化時(shí)會(huì)呈現(xiàn)出什么樣的規(guī)律，那么就需要引入時(shí)間復(fù)雜度的概念。

一般情況下，算法基本操作的重復(fù)執(zhí)行次數(shù)為問(wèn)題規(guī)模n的某個(gè)函數(shù)，也就是用時(shí)間頻度T(n)表示。如果存在某個(gè)函數(shù)f(n)，使得當(dāng)n趨于無(wú)窮大時(shí)，T(n)/f(n)的極限值是不為零的常數(shù)，那么f(n)是T(n)的同數(shù)量級(jí)函數(shù)，記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度。

漸進(jìn)時(shí)間復(fù)雜度用大寫O表示，所以也稱作大O表示法。算法的時(shí)間復(fù)雜度函數(shù)為：T(n)=O(f(n));

T(n)=O(f(n))表示存在一個(gè)常數(shù)C，使得在當(dāng)n趨于正無(wú)窮時(shí)總有 T(n) ≤ C * f(n)。簡(jiǎn)單來(lái)說(shuō)，就是T(n)在n趨于正無(wú)窮時(shí)最大也就跟f(n)差不多大。也就是說(shuō)當(dāng)n趨于正無(wú)窮時(shí)T(n)的上界是C * f(n)。其雖然對(duì)f(n)沒(méi)有規(guī)定，但是一般都是取盡可能簡(jiǎn)單的函數(shù)。

常見(jiàn)的時(shí)間復(fù)雜度有：O(1)常數(shù)型;O(log n)對(duì)數(shù)型，O(n)線性型，O(nlog n)線性對(duì)數(shù)型，O(n2)平方型，O(n3)立方型，O(nk)k次方型，O(2n)指數(shù)型。

上圖為不同類型的函數(shù)的增長(zhǎng)趨勢(shì)圖，隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。

常見(jiàn)的算法時(shí)間復(fù)雜度由小到大依次為：Ο(1)<Ο(log n)<Ο(n)<Ο(nlog n)<Ο(n2)<Ο(n3)<…<Ο(2^n)<Ο(n!)。

值得留意的是，算法復(fù)雜度只是描述算法的增長(zhǎng)趨勢(shì)，并不能說(shuō)一個(gè)算法一定比另外一個(gè)算法高效。這要添加上問(wèn)題規(guī)模n的范圍，在一定問(wèn)題規(guī)范范圍之前某一算法比另外一算法高效，而過(guò)了一個(gè)閾值之后，情況可能就相反了，通過(guò)上圖我們可以明顯看到這一點(diǎn)。這也就是為什么我們?cè)趯?shí)踐的過(guò)程中得出的結(jié)論可能上面算法的排序相反的原因。

如何推導(dǎo)時(shí)間復(fù)雜度

上面我們了解了時(shí)間復(fù)雜度的基本概念及表達(dá)式，那么實(shí)踐中我們?cè)趺礃硬拍芡ㄟ^(guò)代碼獲得對(duì)應(yīng)的表達(dá)式呢?這就涉及到求解算法復(fù)雜度。

求解算法復(fù)雜度一般分以下幾個(gè)步驟：

• 找出算法中的基本語(yǔ)句：算法中執(zhí)行次數(shù)最多的語(yǔ)句就是基本語(yǔ)句，通常是最內(nèi)層循環(huán)的循環(huán)體。
• 計(jì)算基本語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)：只需計(jì)算基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)，即只要保證函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡(jiǎn)化算法分析，使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率。
• 用大Ο表示算法的時(shí)間性能：將基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)放入大Ο記號(hào)中。

其中用大O表示法通常有三種規(guī)則：

• 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù);
• 只保留時(shí)間函數(shù)中的最高階項(xiàng);
• 如果最高階項(xiàng)存在，則省去最高階項(xiàng)前面的系數(shù);

下面通過(guò)具體的實(shí)例來(lái)說(shuō)明以上的推斷步驟和規(guī)則。

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

常數(shù)階O(1)

無(wú)論代碼執(zhí)行了多少行，只要是沒(méi)有循環(huán)等復(fù)雜結(jié)構(gòu)，那這個(gè)代碼的時(shí)間復(fù)雜度就都是O(1)，如：

int i = 1; 
int j = 2; 
int k = 1 + 2; 

上述代碼執(zhí)行時(shí)，單個(gè)語(yǔ)句的頻度均為1，不會(huì)隨著問(wèn)題規(guī)模n的變化而變化。因此，算法時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。這里我們需要注意的是，即便上述代碼有成千上萬(wàn)行，只要執(zhí)行算法的時(shí)間不會(huì)隨著問(wèn)題規(guī)模n的增長(zhǎng)而增長(zhǎng)，那么執(zhí)行時(shí)間只不過(guò)是一個(gè)比較大的常數(shù)而已。此類算法的時(shí)間復(fù)雜度均為O(1)。

對(duì)數(shù)階O(log n)

先來(lái)看對(duì)應(yīng)的示例代碼：

int i = 1; // ① 
while (i <= n) { 
   i = i * 2; // ② 
} 

在上述代碼中，語(yǔ)句①的頻度為1，可以忽略不計(jì)。

語(yǔ)句②我們可以看到它是以2的倍數(shù)來(lái)逼近n，每次都乘以2。如果用公式表示就是122*2…*2 <=n，也就是說(shuō)2的x次方小于等于n時(shí)會(huì)執(zhí)行循環(huán)體，記作2^x <= n，于是得出x<=logn。也就是說(shuō)上述循環(huán)在執(zhí)行l(wèi)ogn次之后，便結(jié)束了，因此上述代碼的時(shí)間復(fù)雜度為O(log n)。

其實(shí)上面代碼的時(shí)間復(fù)雜度公式如果精確的來(lái)講應(yīng)該是：T(n) = 1 + O(log n)，但我們上面已經(jīng)講到對(duì)應(yīng)的原則，“只保留時(shí)間函數(shù)中的最高階項(xiàng)”，因此記作O(log n)。

線性階O(n)

示例代碼：

int j = 0; // ① 
for (int i = 0; i < n; i++) { // ② 
   j = i; // ③ 
   j++; // ④ 
} 

上述代碼中，語(yǔ)句①的頻度為1，②的頻度為n，③的頻度為n-1，④的頻度為n-1，因此整個(gè)算法可以用公式T(n)=1+n+(n-1)+(n-1)來(lái)表示。進(jìn)而可以推到T(n)=1+n+(n-1)+(n-1)=3n-1，即O(n)=3n-1，去掉低次冪和系數(shù)即O(n)=n，因此T(n)=O(n)。

在上述代碼中for循環(huán)中的代碼會(huì)執(zhí)行n遍，因此它消耗的時(shí)間是隨著n的變化而成線性變化的，因此這類算法都可以用O(n)來(lái)表示時(shí)間復(fù)雜度。

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

示例代碼：

for (int m = 1; m < n; m++) { 
   int i = 1; // ① 
   while (i <= n) { 
      i = i * 2; // ② 
   } 
} 

線性對(duì)數(shù)階要對(duì)照對(duì)數(shù)階 O(log n)來(lái)進(jìn)行理解。上述代碼中for循環(huán)內(nèi)部的代碼便是上面講到對(duì)數(shù)階，只不過(guò)在對(duì)數(shù)階的外面套了一個(gè)n次的循環(huán)，當(dāng)然，它的時(shí)間復(fù)雜度就是n*O(log n)了，于是記作O(nlog n)。

平方階O(n²)

示例代碼：

int k = 0; 
for (int i = 0; i < n; i++) { 
   for (int j = 0; j < n; j++) { 
      k++; 
   } 
} 

平方階可對(duì)照線性階來(lái)進(jìn)行理解，我們知道線性階是一層for循環(huán)，記作O(n)，此時(shí)等于又嵌套了一層for循環(huán)，那么便是n * O(n)，也就是O(n * n)，即O(n^2)。

如果將外層循環(huán)中的n改為m，即：

int k = 0; 
for (int i = 0; i < m; i++) { 
   for (int j = 0; j < n; j++) { 
      k++; 
   } 
} 

那么，對(duì)應(yīng)的時(shí)間復(fù)雜度便為：O(m * n)。

同理，立方階O(n³)、K次方階O(n^k)，只不過(guò)是嵌套了3層循環(huán)、k層循環(huán)而已。

排序算法對(duì)比

上面介紹了各種示例算法的時(shí)間復(fù)雜度推理過(guò)程，對(duì)照上面的時(shí)間復(fù)雜度以及算法效率的大小，來(lái)看一下我們常見(jiàn)的針對(duì)排序的幾種算法的時(shí)間復(fù)雜度對(duì)比。

空間復(fù)雜度

最后，我們?cè)倭私庖幌驴臻g復(fù)雜度?？臻g復(fù)雜度主要指執(zhí)行算法所需內(nèi)存的大小，用于對(duì)程序運(yùn)行過(guò)程中所需要的臨時(shí)存儲(chǔ)空間的度量，這里的空間復(fù)雜度同樣是預(yù)估的。

程序執(zhí)行除了需要存儲(chǔ)空間、指令、常數(shù)、變量和輸入數(shù)據(jù)外，還包括對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)計(jì)算所需信息的輔助空間。存儲(chǔ)空間通常包括：指令空間(即代碼空間)、數(shù)據(jù)空間(常量、簡(jiǎn)單變量)等所占的固定部分和動(dòng)態(tài)分配、遞歸棧所需的可變空間。其中可變空間與算法有關(guān)。

一個(gè)算法所需的存儲(chǔ)空間用f(n)表示。S(n)=O(f(n))其中n為問(wèn)題的規(guī)模，S(n)表示空間復(fù)雜度。

下面看兩個(gè)常見(jiàn)的空間復(fù)雜度示例：空間復(fù)雜度O(1)和O(n)。

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

空間復(fù)雜度為O(1)的情況的示例代碼與時(shí)間復(fù)雜度為O(1)的實(shí)例代碼一致：

int i = 1; 
int j = 2; 
int k = 1 + 2; 

上述代碼中臨時(shí)空間并不會(huì)隨著n的變化而變化，因此空間復(fù)雜度為O(1)?？偨Y(jié)一下就是：如果算法執(zhí)行所需要的臨時(shí)空間不隨著某個(gè)變量n的大小而變化，此算法空間復(fù)雜度為一個(gè)常量，可表示為 O(1)，即 S(n) = O(1)。

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

示例代碼：

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

上述代碼中，只有創(chuàng)建int數(shù)組分配空間時(shí)與n的大小有關(guān)，而for循環(huán)內(nèi)沒(méi)有再分配新的空間，因此，對(duì)應(yīng)的空間復(fù)雜度為S(n) = O(n)。

總結(jié)一下

本篇文章給大家講了可以通過(guò)時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)衡量算法的優(yōu)劣，同時(shí)用具體的實(shí)例來(lái)講解如何計(jì)算不同方法的時(shí)間復(fù)雜度和空間復(fù)雜度。當(dāng)我們了解了這些基本的概念、函數(shù)、計(jì)算方法、計(jì)算規(guī)則及算法性能之后，再進(jìn)行算法的學(xué)習(xí)便可以輕松預(yù)估出算法的性能等指標(biāo)。

參考文獻(xiàn)：

https://blog.csdn.net/zolalad/article/details/11848739

https://zhuanlan.zhihu.com/p/50479555