一、前言

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

衡量不同算法之間的優(yōu)劣主要是通過時間和空間兩個維度去考量：

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

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

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

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

二、時間復(fù)雜度

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

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

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

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

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

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

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

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，那么時間復(fù)雜度為O(n + 3)，又因?yàn)闀r間復(fù)雜度只關(guān)注最高數(shù)量級，且與之系數(shù)也沒有關(guān)系，因此上述的時間復(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次，因此時間復(fù)雜度為?O(n*n*1 + 2) = O(n^2)

對于順序執(zhí)行的語句，總的時間復(fù)雜度等于其中最大的時間復(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)

又如下一個例子：

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

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

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

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

三、空間復(fù)雜度

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

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

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

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

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

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

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

通常來說，只要算法不涉及到動態(tài)分配的空間，以及遞歸、棧所需的空間，空間復(fù)雜度通常為O(1)，一個一維數(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

如果對您有所幫助，歡迎您點(diǎn)個關(guān)注，我會定時更新技術(shù)文檔，大家一起討論學(xué)習(xí)，一起進(jìn)步。

?文章來源地址http://www.zghlxwxcb.cn/news/detail-845715.html

到了這里，關(guān)于說說你對算法中時間復(fù)雜度，空間復(fù)雜度的理解？如何計(jì)算？的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！