「算法與數據結構」時間與空間復雜度
本文轉載自微信公眾號「 不正經的前端」，作者 不正經的前端。轉載本文請聯系 不正經的前端公眾號。
寫在前面
可能有些人會吐槽，學算法有什么用，頂多就是去面試大廠的時候能用上，大廠面試算法也只是強中篩強的一個敲門磚而已，我又不去面大廠，不用學它，真的是這樣嗎?
肯定不是，在計算機行業發展，不管是前端亦或是后端，算法都是進階的一個絆腳石，可以說不會算法永遠也成不了一個合格的高級工程師，想要進大廠確實要會些算法，但是它并不只是為了面試，它和我們的程序是息息相關的，有人說前端不需要算法?你把大名鼎鼎的 虛擬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
「例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 的大小向數組 arr 中 push 元素，所以，n 多大，數組就有多少元素，就占用了多少空間，所以空間復雜度S(n) = O(n)
「空間復雜度小結」
空間復雜度里，只列出了兩個例子，是因為一般情況下，我們用不到其他的，空間復雜度一般只會是 O(1)/O(n)/O(n^2)，其它的很少見，當然也有，我們在知道了時間復雜度再分析空間復雜度也很好分析，就不過多贅述了
關于分析空間復雜度，其實我們直接從聲明的變量入手就可以，看函數體內聲明的變量根據傳入值的變化而變化來分析
另外，這里我們沒有列舉遞歸情況，「請注意」，遞歸就是函數套函數，像俄羅斯套娃一樣的，這中間其實有一個問題，我們知道，遞歸函數，每層遞歸里都會開辟一個遞歸棧，每次遞歸產生的變量等空間消耗都會存在遞歸棧中，這也是一個空間，不管你有沒有聲明變量，只要遞歸了遞歸棧它都存在，也就是說只要存在遞歸的情況，基本上最少的空間復雜度也是 O(n) 了，所以我們盡可能的在能使用迭代的情況下就不使用遞歸
時間 VS 空間
開頭我們說了，評價一個算法的效率我們主要是從它的時間和空間兩個維度看，但是，通常我們在算法中，時間和空間就是魚和熊掌的關系，這時候可能一道算法題有兩種解法，一種時間復雜度低，但空間復雜度稍高，另一種則反之
這個時候怎么辦呢?細品就知道了，在開發中，我們一般都是時間優于空間的，你想啊，一個程序，用戶不會關心的占用了多少內存，但是他會關心你這個程序他在使用時的執行速度，況且，空間也就是磁盤，現階段磁盤我們可以花錢擴容，時間上就沒這么簡單了，所以某些相對的情況下，空間換時間是可以令人接受的
雖說空間換時間可行，但也不能一味的空間換時間，我們還是要盡可能降低兩個維度的復雜度，少數對立情況下，可空間換時間
我們在刷算法的時候，不是刷完了就完事了，我們還要去分析我們的題解對應的時間及空間復雜度，可以分析多種題解之間的復雜度，對比找出最優解
在面試的時候，假如面試官給你一道算法題，當你知道好幾種解法的時候，完全可以很裝B的問一下，您喜歡時間至上還是空間至上呢，我都能解，奧利給，說完他就會讓你都寫了??
開個玩笑哈，面試的時候盡量寫出多種解法并給面試官解釋各種解法時間及空間復雜度的不同，怎么說?就很棒
最后
此文介紹算法一些理論基礎，理解之后就可以刷題了，推薦按照數據結構類型來每天刷一題，建議上班無聊時刷題，上班摸魚水群不如摸魚刷道算法，百利無一害，堅持每天刷題吧，加油
GitHub建了個算法倉庫，從零更算法題/文字/視頻 題解ing，一塊來刷吧 ?? GitHub傳送門[1]
準備算法每篇每題都錄個視頻版，主要是為了跟思路講一遍手寫下，講的可能不好，此文視頻詳見 ?? B站傳送門[2]
看到這里了，來個三連吧，如有錯誤請指正，也歡迎大家關注公眾號「不正經的前端」，和算法群的朋友們組團刷算法，效率更高
Reference
[1]GitHub傳送門:
https://github.com/isboyjc/DailyAlgorithms
[2]B站傳送門:
https://www.bilibili.com/video/BV1T5411p7oN
