[[424483]]

一、前言

算法(Algorithm)是指用來(lái)操作數(shù)據(jù)、解決程序問(wèn)題的一組方法。對(duì)于同一個(gè)問(wèn)題，使用不同的算法，也許最終得到的結(jié)果是一樣的，但在過(guò)程中消耗的資源和時(shí)間卻會(huì)有很大的區(qū)別。

衡量不同算法之間的優(yōu)劣主要是通過(guò)「時(shí)間」和「空間」兩個(gè)維度去考量：

• 時(shí)間維度：是指執(zhí)行當(dāng)前算法所消耗的時(shí)間，我們通常用「時(shí)間復(fù)雜度」來(lái)描述。
• 空間維度：是指執(zhí)行當(dāng)前算法需要占用多少內(nèi)存空間，我們通常用「空間復(fù)雜度」來(lái)描述

通常會(huì)遇到一種情況，時(shí)間和空間維度不能夠兼顧，需要在兩者之間取得一個(gè)平衡點(diǎn)是我們需要考慮的

一個(gè)算法通常存在最好、平均、最壞三種情況，我們一般關(guān)注的是最壞情況

最壞情況是算法運(yùn)行時(shí)間的上界，對(duì)于某些算法來(lái)說(shuō)，最壞情況出現(xiàn)的比較頻繁，也意味著平均情況和最壞情況一樣差

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

時(shí)間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的計(jì)算工作量，其復(fù)雜度反映了程序執(zhí)行時(shí)間「隨輸入規(guī)模增長(zhǎng)而增長(zhǎng)的量級(jí)」，在很大程度上能很好地反映出算法的優(yōu)劣與否

一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的「執(zhí)行次數(shù)成正比」，執(zhí)行次數(shù)越多，花費(fèi)的時(shí)間就越多

算法的復(fù)雜度通常用大O符號(hào)表述，定義為T(n) = O(f(n))，常見(jiàn)的時(shí)間復(fù)雜度有：O(1)常數(shù)型、O(log n)對(duì)數(shù)型、O(n)線性型、O(nlogn)線性對(duì)數(shù)型、O(n^2)平方型、O(n^3)立方型、O(n^k)k次方型、O(2^n)指數(shù)型，如下圖所示：

從上述可以看到，隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低，由小到大排序如下：

Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!) 

注意的是，算法復(fù)雜度只是描述算法的增長(zhǎng)趨勢(shì)，并不能說(shuō)一個(gè)算法一定比另外一個(gè)算法高效，如果常數(shù)項(xiàng)過(guò)大的時(shí)候也會(huì)導(dǎo)致算法的執(zhí)行時(shí)間變長(zhǎng)

關(guān)于如何計(jì)算時(shí)間復(fù)雜度，可以看看如下簡(jiǎn)單例子：

function process(n) { 
  let a = 1 
  let b = 2 
  let sum = a + b 
  for(let i = 0; i < n; i++) { 
    sum += i 
  } 
  return sum 
} 

該函數(shù)算法需要執(zhí)行的運(yùn)算次數(shù)用輸入大小n的函數(shù)表示，即 T(n) = 2 + n + 1，那么時(shí)間復(fù)雜度為O(n + 3)，又因?yàn)闀r(shí)間復(fù)雜度只關(guān)注最高數(shù)量級(jí)，且與之系數(shù)也沒(méi)有關(guān)系，因此上述的時(shí)間復(fù)雜度為O(n)

又比如下面的例子：

function process(n) { 
 let count = 0 
  for(let i = 0; i < n; i++){ 
    for(let i = 0; i < n; i++){ 
      count += 1 
    } 
  } 
} 

循環(huán)里面嵌套循環(huán)，外面的循環(huán)執(zhí)行一次，里面的循環(huán)執(zhí)行n次，因此時(shí)間復(fù)雜度為 O(n*n*1 + 2) = O(n^2)

對(duì)于順序執(zhí)行的語(yǔ)句，總的時(shí)間復(fù)雜度等于其中最大的時(shí)間復(fù)雜度，如下：

function process(n) { 
  let sum = 0 
  for(let i = 0; i < n; i++) { 
    sum += i 
  } 
  for(let i = 0; i < n; i++){ 
    for(let i = 0; i < n; i++){ 
      sum += 1 
    } 
  } 
  return sum 
} 

上述第一部分復(fù)雜度為O(n)，第二部分復(fù)雜度為O(n^2)，總復(fù)雜度為max(O(n^2), O(n)) = O(n^2)

又如下一個(gè)例子：

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

循環(huán)語(yǔ)句中以2的倍數(shù)來(lái)逼近n，每次都乘以2。如果用公式表示就是1 * 2 * 2 * 2 … * 2 <=n，也就是說(shuō)2的x次方小于等于n時(shí)會(huì)執(zhí)行循環(huán)體，記作2^x <= n，于是得出x<=logn

因此循環(huán)在執(zhí)行l(wèi)ogn次之后，便結(jié)束，因此時(shí)間復(fù)雜度為O(logn)

同理，如果一個(gè)O(n)循環(huán)里面嵌套O(logn)的循環(huán)，則時(shí)間復(fù)雜度為O(nlogn)，像O(n^3)無(wú)非也就是嵌套了三層O(n)循環(huán)

三、空間復(fù)雜度

空間復(fù)雜度主要指執(zhí)行算法所需內(nèi)存的大小，用于對(duì)程序運(yùn)行過(guò)程中所需要的臨時(shí)存儲(chǔ)空間的度量

除了需要存儲(chǔ)空間、指令、常數(shù)、變量和輸入數(shù)據(jù)外，還包括對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)計(jì)算所需信息的輔助空間

下面給出空間復(fù)雜度為O(1)的示例，如下

let a = 1 
let b = 2 
let c = 3 

上述代碼的臨時(shí)空間不會(huì)隨著n的變化而變化，因此空間復(fù)雜度為O(1)

let arr [] 
for(i=1; i<=n; ++i){ 
  arr.push(i) 
} 

上述可以看到，隨著n的增加，數(shù)組的占用的內(nèi)存空間越大

通常來(lái)說(shuō)，只要算法不涉及到動(dòng)態(tài)分配的空間，以及遞歸、棧所需的空間，空間復(fù)雜度通常為O(1)，一個(gè)一維數(shù)組a[n]，空間復(fù)雜度O(n)，二維數(shù)組為O(n^2)

參考文獻(xiàn)

• https://juejin.cn/post/6844904167824162823#heading-7
• https://zhuanlan.zhihu.com/p/50479555
• https://cloud.tencent.com/developer/article/1769988