「算法與數據結構」時間與空間複雜度

語言: CN / TW / HK

寫在前面

可能有些人會吐槽,學算法有什麼用,頂多就是去面試大廠的時候能用上,大廠面試算法也只是強中篩強的一個敲門磚而已,我又不去面大廠,不用學它,真的是這樣嗎?

肯定不是,在計算機行業發展,不管是前端亦或是後端,算法都是進階的一個絆腳石,可以説不會算法永遠也成不了一個合格的高級工程師,想要進大廠確實要會些算法,但是它並不只是為了面試,它和我們的程序是息息相關的,有人説前端不需要算法?你把大名鼎鼎的 虛擬DOM (Virtual DOM) 置於何地,它就是 算法與數據結構 的一種體現,可能又有人會説了,我又不寫虛擬DOM。。。嗯,那你總想要賺錢吧,走技術路線想拿高薪,算法是基石

網上有很多算法文章以及課程,説 7 天學會算法數據結構,30 天掌握算法與數據結構等等等等,別傻了,算法沒有捷徑,只能靠我們一點一點累積,你要做的首先就是相信自己不是天才,其次是每天堅持刷題,時間緊可以一週刷四五題,最好速度是每天一題,後期時間充裕或者熟練了甚至可以一天刷幾題,即使很聰明的人在一段時間不接觸算法後,還是會忘掉,所以重要的是持續下去

接下來我們來從零開始學習算法吧,如果你未曾刷過算法,這篇文章會帶你瞭解什麼是算法,什麼是數據結構,在刷算法的同時,我們要明確自己的解法是否足夠優質,而判斷優質解發會通過時間以及空間兩個維度來體現,本文更會重點介紹,這些都是刷算法之前需要必備的知識,如果能為你的算法之路帶來啟蒙,那真是太棒了,十分榮幸,如果你已經瞭解了這些知識,那麼不妨快速閲讀下,看看是否能為你的算法知識做些擴充,當然如果有錯誤的地方,你也可以為我指引,更是十分榮幸

什麼是數據結構

數據結構其實就是是程序存儲組織數據的方式,一個數據結構是由程序中的數據元素按照某種邏輯關係組織起來的,是若干個數據元素的組合

數據結構是程序中處理數據的基本單位,在程序中作為一個整體來使用

例如一個數字 1 或者一個字符 A,它是一種數據結構

例如一個日期 2020年12月14日,它由年月日這 3 種格式組成,也是一種數據結構

例如一個數組 [1, 'a', '2020年12月14日'],它是由數字、字符、日期格式組合而成,也是一種數據結構

通俗來説,用一定格式組成的數據都是數據結構,我們比較常見的數據結構有字符串、數組、對象、堆、棧、鏈表、樹、哈希表等等,你可能對着其中的一些數據結構並不瞭解,不要擔心,你並不需要立刻知道它們都是什麼,對於前端來説,我們使用 JavaScript 這個令我們又愛又恨的語言,它本身就存在的數據結構很少,那麼對於像鏈表、樹等等這些結構都是通過對象來模擬的,這點要先知道

在許多程序設計當中,數據結構的選擇是一個基本的設計考慮因素,系統實現的困難程度和系統構造的質量都嚴重依賴於是否選擇了最優的數據結構,選擇最優的數據結構能夠有效的提高運行的效率和節約存儲空間的使用,但是要知道,沒有十全十美的數據結構,每種數據結構都有侷限性同樣也有優點,要根據需求來選擇合適的數據結構

什麼是算法

什麼是算法,我們都知道 1+2+3=6,為什麼等於 6 呢,你可能會説,1 加 2等於 3,兩個 3 相加等於 6,這是小學生都會的數學常識,它就是廣義上的算法

算法其實就是解決一個問題的完整步驟描述,是指完成一個任務準確而完整的步驟描述

算法的設計很多時候需要取決於數據結構,而算法的實現更依賴於採用的數據結構

提出一個問題的算法是一個從抽象到具體的過程

  • 分析問題,選擇數據結構,得出初步的解決方法

  • 將解決方法合理地拆分,整理成許多步驟

  • 為重複的步驟選擇合理的循環變量

  • 使用易轉化為程序實現的自然語言簡練地描述算法

瞭解了什麼是算法之後,我們來看時間和空間複雜度,衡量不同算法之間的優劣我們通常從兩個維度來考究

  • 時間維度:指執行代碼所消耗的時間,即時間複雜度
  • 空間維度:指執行代碼所消耗的空間,即空間複雜度

接下來就開始逐步剖析時間和空間複雜度了,先説時間複雜度

時間複雜度

在説時間複雜度之前,我們首先要理解一個概念即代碼執行次數,也可稱之為語句頻度或時間頻度,用 T(n) 表示

我們用例子來一步一步闡述,首先我們來看函數 fn1

function fn1(){
  console.log("句末")
  console.log("isboyjc")
}
複製代碼

我們來看這個函數中的語句會執行多少次

很明顯此函數內部只有兩個語句,即 console.log("句末")console.log("isboyjc"),那麼我們説這個函數體內代碼執行次數是 2

我們再來看函數 fn2

function fn2(n){
  for(let i = 0; i < n; i++){
    console.log("句末")
  }
}
複製代碼

我們先來看函數 fn2 中有幾條可執行語句

let i = 0
i < n
i++
console.log("句末")
複製代碼

我們假設 n = 3,然後依次帶入進去,看看各個執行語句執行了多少次

let i = 0 此條聲明語句只在第一次 for 循環聲明時執行 1 次

i < n 此條語句執行次數根據形參 n 的大小變化,n = 3 時,即 i=0,i=1,i=2,i=3 時會執行,即此條語句執行次數為 n + 1

i++ 此條語句執行次數也是根據形參 n 的大小變化,n = 3 時,即 i=0,i=1,i=2 時會執行,即 n 次

console.log("句末") 此條語句執行次數還是根據形參 n 的大小變化,n = 3 會執行 3 次,那麼此語句在函數內部即會執行 n 次

1 + (n + 1) + n + n = (3n + 2)
複製代碼

那麼函數 fn2 內共執行 3n + 2

一段代碼的總執行次數我們通常會用 T(n) 來表示,那麼調用一次上面 fn1/fn2 兩函數的總執行次數即

T(n) = 2	// fn1
T(n) = 3n + 2 	// fn2
複製代碼

上面的 n,指的是為問題的規模,即輸入數據的大小或者説數量,你也可以簡單的理解為 T 就是函數本身,n 就是參數,也就是説

函數 fn1 任何情況下執行次數都為 2

函數 fn2 的總執行次數會根據 n 的大小變化而產生一個變化

我們思考一下,我們可以使用一段代碼的執行總次數來衡量執行速度嗎?

答案當然是不行的,當代碼行數比較多的時候,我們一條一條的數來計算執行總次數太麻煩了,例如函數中套用函數時、循環中套用循環時,想要精確計算執行次數都是非常麻煩的

所以,在算法中,我們一般用 T(n) 簡化後的估算值來表達代碼執行的速度,通常我們用大些字母 O 來表示,即大 O 表示法,由於是估算,它表示的是代碼執行時間隨數據規模增長的變化趨勢,所以,也叫作漸進時間複雜度(asymptotic time complexity),簡稱時間複雜度

明確了這個概念以後,我們就可以來算時間複雜度了,還是用上面 fn1/fn2 兩函數例

// fn1
T(n) = 2

// fn2
T(n) = 3n + 2
複製代碼

首先我們來看函數 fn1,它的執行總次數為 2,一個 常數(常數級),也就是説此函數無論何時它的總執行次數都是 2,是一個不變的值,那麼我們使用時間複雜度 O 來表示時直接估算為 1 就可以,即時間複雜度為 O(1)

我們再來看函數 fn2 ,它的執行次數 T(n)3n + 2常數*n + 常數,這裏我們完全可以看成 常數*n+常數 兩部分,隨着 n 的增大,只有前一個部分會有變化,後面是不變的,所以在表示時間複雜度時就可以忽略後面不變的常數,即 常數*n,而 常數*n 中過的常數我們也可以直接當做 1,或者説忽略掉這個作為係數的常數,那麼最終可以得出函數 fn2 的時間複雜度為 n,即 O(n)

PS:曉得可能有人把數學知識還給老師了,所以解釋下

常數: 常數就是指平常的數值,可簡單的理解為固定不變的數值

係數: 係數指代數式的單項式中的數字因數,例如 a = 1 * a ,則它的係數為 1,2b = 2 * b ,則它的係數為 2

我們再來舉個例子,如下面這個多項式代指一個函數的 T(n),求它的時間複雜度

T(n) = 10n^4 + 100n^2 + 1000
複製代碼

其實,對於多項式,我們只需要保留最高次項就行了,也就説,保留 n 的最高次方數就可以了,這個例子中保留的也就是 n 的 4 次方,係數和常數皆可以忽略,最終得到的時間複雜度即為 O(n^4)

結論:

T(n) 為常數時,時間複雜度為 O(1) ,反之時間複雜度為 O(保留T(n)的最高次項並去掉最高次項的係數)

接下來,我們看幾個例子來判斷下幾段代碼的時間複雜度

例1:

function fn01(){
  console.log("你看這是啥")
  console.log("這是一個輸出")
  console.log("哈哈哈")
  let a = 1
  return a
}
複製代碼

上面這個函數 fn01 中只有一條條的語句,共執行 5 次,毫無變化,時間複雜度即 O(1) ,此為常數級時間複雜度

例2:

function fn02(n){
  for(let i = 0; i < n; i++){
    console.log("這是一個輸出🎓")
  }
}
複製代碼

如上,函數 fn02 同上文中的例子 fn2,一個循環,時間複雜度即為 O(n) ,此為線性級時間複雜度

例3:

function fn03(n){
  for(let i = 0; i < n; i++){
    console.log("外層循環")
    for(let j = 0; j < n; j++){
      console.log("內層循環")
    }
  }
}
複製代碼

這個題和上面就不太一樣了,我們先單獨看內部的循環,內部循環大概會執行 n 次,再來看外部循環又會執行 n 次,最終也就是 n * n = n^2,即函數 fn03 的時間複雜度為 O(n^2) ,此為平方級時間複雜度,如果是三層循環也就是時間複雜度為 O(n^3) 時,即立方級時間複雜度

從這裏我們就可以看出來,一段代碼有多少層循環,時間複雜度就是 n 的多少次方,所以儘量避免多層循環嵌套

例4:

我們再來看下面這個函數 fn04

function fn04(n){
  for(let i = 0; i < n; i++){
    console.log("外層循環")
    for(let j = 0; j < n; j++){
      console.log("內層循環")
    }
  }
  
  for(let i = 0; i < n; i++){
    console.log("哈哈哈")
  }
}
複製代碼

此函數中有一個雙循環,有一個單循環,即執行次數大概是 n^2 + n,根據我們上面説的保留最高次項,那麼函數 fn04 的時間複雜度即為 O(n^2)

例5:

算法中肯定不只是上面那種尋常的循環,再來看下面這一個

function fn05(n){
  for(let i = 0; i < n; i++){
    console.log("外層循環")
    for(let j = i; j < n; j++){
      console.log("內層循環")
    }
  }
}
複製代碼

其實遇到這種,我們直接帶入進去試一試即可知其規律

i = 0 時,裏層循環會執行 n 次

i = 1 時,裏層循環會執行 n - 1 次

i = 2 時,裏層循環會執行 n - 2 次

i = 3 時,裏層循環會執行 n - 3 次

這個時候我們就發現了規律,每當 i 增加 1,裏層循環就少執行 1 次,那麼就簡單了

i = n - 2 時,裏層循環會執行 2 次

i = n - 1 時,裏層循環會執行 1 次

最終我們把 n 個裏層循環的執行次數相加即可得出最終的一個不精確的總執行次數

T(n) = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1
複製代碼

如上,這是一個等差數列,嗯,曉得,會補充

如果一個數列從第二項起,每一項與它的前一項的差等於同一個常數,這個數列就叫做等差數列,而這個常數叫做等差數列的公差,公差常用字母 d 表示

例如:1,3,5,7,9……(2n-1) ,等差數列 S(n) 的通項公式為:S(n) = S1 + (n-1) * d,前 n 項和公式如下

S(n) = n*S1 + n*(n - 1)*d/2

// 或

S(n) = n*(S1 + Sn)/2
複製代碼

如此我們計算結果就成,我們上面的數列中,公差 d 為 -1,帶入公式即可,第二個公式簡單,用第二個好了,計算結果都是一樣的

// n*(S1 + Sn)/2

n*(n + 1)/2 = (n^2 + n)/2 = (1/2)n^2 + (1/2)n
複製代碼

最終我們得到了 (1/2)n^2 + (1/2)n ,按照上文中取最高次項去掉係數,即時間複雜度為 O(n^2)

例6:

再來看一個例子

function fn06(n){
  for(let i = 1; i < n; i *= 2){
    console.log("isboyjc")
  }
}
複製代碼

還是老樣子,如果你不曉得怎麼看,可以先帶入幾個參數試一下,看一看規律

我們可以分別使用 n=2, n=4, n=8, n=16,觀察其循環中打印次數,當然你也可以直接運行一下代碼,過程不過多闡述了,我們直接看結果

n=2		時打印1次 T(n)=1
n=4		時打印2次 T(n)=2
n=8		時打印3次 T(n)=3
n=16 		時打印4次 T(n)=4
複製代碼

對於執行次數產生主要影像的就是循環語句中的 i*=2,每次循環 i 都會變成自身的兩倍,仔細觀察我們就可以得出這樣一個規律性結果

n=2		時打印1次 T(n)=1 // 2^1 = 2
n=4		時打印2次 T(n)=2 // 2^2 = 4
n=8		時打印3次 T(n)=3 // 2^3 = 8
n=16 		時打印4次 T(n)=4 // 2^4 = 16
複製代碼

根據上面的規律我們不難發現,那麼2^執行次數=n,即 2^T(n)=n ,我們求 T(n),調個就行了,也就是以 2 為底 n 的對數,即 T(n)=log_2 n

PS:又來補數學了

對數: 假如 a^n=b,即 a 的 n 次方等於 b,我們求 n 的值,那麼這裏為了方便表示就可以寫成 log_a b,即以 a 為底 b 的對數,a 是底數,b 是真數,而 n 就是對數

你可能會在糾結為什麼只觀察循環中的打印次數而不計算其所有的執行次數,原因上面也説過了,這些固有的常數及係數完全可以忽略,好吧,我們再最後推一遍

中間輸出為 log_2 n 次,let i = 1 只會執行一次,i<n 會執行 log_2 n + 1 次,i*=2 也會執行 log_2 n 次,加起來就是 log_2 n + log_2 n + 1 + log_2 n,即 3log_2 n + 2,除去係數 3 和常數 2,我們得出了 log_2 n ,在時間複雜度的計算中 log 的底數也是可以省略的,所以最終函數 fn06 的時間複雜度為 O(log n) ,也就是對數級時間複雜度

例7:

最後在給大家來一個例子吧

function fn07(n,m){
  for(let i = 0; i < n; i++){
    while(j < m){
      console.log("你看懂了嗎")
      j = j * 2
    }
  }
}
複製代碼

如上圖,此函數有兩個參數,對應了裏外兩個循環,我們先從內部循環看起,眼熟嗎?其實內部循環和上題函數 fn06 中的循環是一樣的,只是一個用的 for ,一個用的 while,上題中的時間複雜度我們就不再敍述了,那麼內層循環時間複雜度為 O(log n)

我們再來看外層循環,也是上面解釋過的,單看外層循環時間複雜度是 O(n)

兩個循環是嵌套關係,相乘就可以了,所以函數 fn07 的時間複雜度即為 O(n*log n) ,也就是線性對數級時間複雜度

正如此函數輸出,你看懂了嗎?

碼字太累,看個圖吧:

找了一張網圖(侵刪),使用圖表來更加清晰的展示了常見的時間複雜度曲線

如上圖,橫座標為 n ,可以看到,不同時間複雜度隨着 n 的增大操作次數或者説執行時間的遞增趨勢

常見的時間複雜度量級有

  • 常數級 O(1)
  • 對數級 O(log n)
  • 線性級 O(n)
  • 線性對數級 O(n*log n)
  • 平方級 O(n^2)
  • 立方級 O(n^3)
  • K次方級 O(n^k)
  • 指數級 O(2^n)

上面從上到下依次時間複雜度越來越大,執行效率越來越低,大部分常用的在上面的圖表中都有展示

所以在程序或是刷題中,我們應該儘量使用低時間複雜度的方法

時間複雜度就到此為止了,我們也列舉了常見的時間複雜度,接下來我們來看看空間複雜度

空間複雜度

空間複雜度其實就是對一個算法或者説一段代碼在運行過程中佔用存儲空間大小表達方式

我們上面講過了時間複雜度,那麼再來説空間複雜度會簡單的很多

空間複雜度也就是 S(n) ,它同樣會用大O表示法來表示,我們直接上例子

例1:

function fn001(n){
  for(let i = 0; i < n; i++){
    console.log("空間複雜度")
  }
}
複製代碼

首先,我們知道,空間複雜度和存儲空間有關,而存儲空間是由什麼決定的,肯定是聲明的變量啊,我們直接來找函數 fn001 中的變量聲明,只有一個 i ,也就是説此函數只有開闢了一塊空間供 i 使用,那麼空間複雜度 S(n) 即為 O(1) ,你可能會説 i 不是一直在變嗎,是的它是在變,但是不管怎麼變,它還是一個數字,佔用空間大小都一致

空間複雜度和時間複雜度一樣,當代碼裏聲明的變量是一個常量,不會根據傳入值的變化而變化,那麼也它的空間複雜度是 O(1)

例2:

function fn002(n){
  let arr = []
  while(n--){
    arr.push(n)
  }
}
複製代碼

這個例子中我們聲明瞭一個數組,我們知道數組中是可以存各種類型的,在循環中,我們根據 n 的大小向數組 arrpush 元素,所以,n 多大,數組就有多少元素,就佔用了多少空間,所以空間複雜度S(n) = O(n)

空間複雜度小結

空間複雜度裏,只列出了兩個例子,是因為一般情況下,我們用不到其他的,空間複雜度一般只會是 O(1)/O(n)/O(n^2),其它的很少見,當然也有,我們在知道了時間複雜度再分析空間複雜度也很好分析,就不過多贅述了

關於分析空間複雜度,其實我們直接從聲明的變量入手就可以,看函數體內聲明的變量根據傳入值的變化而變化來分析

另外,這裏我們沒有列舉遞歸情況,請注意,遞歸就是函數套函數,像俄羅斯套娃一樣的,這中間其實有一個問題,我們知道,遞歸函數,每層遞歸裏都會開闢一個遞歸棧,每次遞歸產生的變量等空間消耗都會存在遞歸棧中,這也是一個空間,不管你有沒有聲明變量,只要遞歸了遞歸棧它都存在,也就是説只要存在遞歸的情況,基本上最少的空間複雜度也是 O(n) 了,所以我們儘可能的在能使用迭代的情況下就不使用遞歸

時間 VS 空間

開頭我們説了,評價一個算法的效率我們主要是從它的時間和空間兩個維度看,但是,通常我們在算法中,時間和空間就是魚和熊掌的關係,這時候可能一道算法題有兩種解法,一種時間複雜度低,但空間複雜度稍高,另一種則反之

這個時候怎麼辦呢?細品就知道了,在開發中,我們一般都是時間優於空間的,你想啊,一個程序,用户不會關心的佔用了多少內存,但是他會關心你這個程序他在使用時的執行速度,況且,空間也就是磁盤,現階段磁盤我們可以花錢擴容,時間上就沒這麼簡單了,所以某些相對的情況下,空間換時間是可以令人接受的

雖説空間換時間可行,但也不能一味的空間換時間,我們還是要儘可能降低兩個維度的複雜度,少數對立情況下,可空間換時間

我們在刷算法的時候,不是刷完了就完事了,我們還要去分析我們的題解對應的時間及空間複雜度,可以分析多種題解之間的複雜度,對比找出最優解

在面試的時候,假如面試官給你一道算法題,當你知道好幾種解法的時候,完全可以很裝B的問一下,您喜歡時間至上還是空間至上呢,我都能解,奧利給,説完他就會讓你都寫了😄

開個玩笑哈,面試的時候儘量寫出多種解法並給面試官解釋各種解法時間及空間複雜度的不同,怎麼説?就很棒

最後

此文介紹算法一些理論基礎,理解之後就可以刷題了,推薦按照數據結構類型來每天刷一題

建議上班無聊時刷題,上班摸魚水羣不如摸魚刷道算法,百利無一害,堅持每天刷題吧,加油

GitHub算法倉庫,使用JavaScript從零更算法題/文字/視頻 題解ing,來關注吧 👉 GitHub傳送門

此文及以後刷的每題都有視頻版,主要是為了跟思路講一遍手寫一下,講的可能不好,詳見 👉 B站傳送門

看到這裏了,來個三連吧,如有錯誤請指正,也歡迎大家關注公眾號「不正經的前端」,和算法羣的朋友們組團刷算法,效率更高