李叔叔之資料結構與算法：時間複雜度與空間複雜度2

• 基礎概念
• • • 舉個例子
    • 散清單(哈希表)
• 空間複雜度
• • 空間複雜度的計算
  • • 常量空間
    • 線性空間
    • 二維空間
    • 遞歸空間
  • 時間與空間的取舍
• 總結

基礎概念

通過上一節的學習，可以了解到時間複雜度和空間複雜度實際上就是時間成本與空間成本，那麼這一節主要說一下空間複雜度。

程式在運作的過程中除了需要執行各種各樣的指令，同時也會根據實際情況，開辟出一些空間，存儲一些

臨時資料

，這樣做的好處是通過臨時資料可以加快通路速度，減少開銷。

那麼什麼時候需要這些臨時資料呢？

舉個例子

假定存在一個整數列，其中有且僅有2個整數是重複的，要求找出這2個整數：

看到這個題目，最容易被大衆所想到的算法就是雙重循環，通過周遊整個數列，每周遊到一個整數，就把它與之前所有周遊過的整數逐一比較，判斷是否重複。

數列：[5,1,2,6,7,3,6]
第一步：周遊第一個整數5，前面沒有數字，是以無法回顧。
第二步：周遊第二個整數1，回顧前面的整數5，沒有重複。
第三步：周遊第三個整數2，回顧前面的整數5,1，沒有重複。
...
第七步：周遊第七個整數6，回顧前面的整數5,1,2,6,7,3，發現與6重複了，得到結果[6，6]。
           

乍一看好像這個算法并沒有什麼問題，但是我們來看看它的時間複雜度是多少呢?

通過上一節的内容我們不難看出，數列每多一個整數，就會多循環周遊一次前面所有的整數，這個算法的時間複雜度是：O(n^2)

而O(n^2)是上一節講到的4種時間複雜度裡效率最低的一個，是以剛才這種算法并不是一個好的算法。

那麼如何提高算法的效率呢？

這時，我們就需要一些臨時資料了。

散清單(哈希表)

還是剛才的題目，當周遊整個數列時，我們可以将周遊過的整數找一個類似“字典”的資料結構給存儲起來，并将“字典”的Key設為整數的值，而将Value設為整數出現的次數，如果之前出現過這個整數，則Value值+1，這樣在進行下一次周遊的時候，就不需要再去回顧比較前面的整數，隻需要一次周遊，就可以得到每個整數出現重複的次數。

周遊[5,1,2,6,7,3,6]，得到：

K V

5 1

1 1

2 1

6 2

7 1

3 1

當把數列周遊完，就可以很清晰的看到6出現了2次，那麼這種算法的時間複雜度是多少呢？

由于隻有1次周遊行為，是以整個算法的時間複雜度是O(n)，相比較之前的O(n^2)，在算法的效率上是有質的提升的。

而剛才所用到的“字典”，是一種特殊的資料結構，叫

散清單

，也叫

哈希表

，這個資料結構是需要開辟一定的記憶體空間來存儲資料資訊的。

空間複雜度

但是記憶體空間也是有限的資源，自然是用的越少越好，而描述一個算法的記憶體空間所用大小，就用到了一個重要的名額：

空間複雜度

。

和時間複雜度類似，空間複雜度是算法在運作過程中臨時占用存儲空間大小的量度，它同樣使用了大O表示法。

程式占用空間大小的計算公式記作：S(n) = O(f(n))

其中n為問題的規模，f(n)為算法所占用存儲空間的函數。

是不是又懵了？沒事，習慣成自然，用多了自然就會了，接着看。

空間複雜度的計算

常見的空間複雜度有以下幾種情形：

常量空間

當算法的存儲空間大小固定，和輸入規模沒有直接關系時，空間複雜度記作：O(1)

線性空間

當算法配置設定的空間是一個線性的集合(或數組)，并且集合的大小和輸入規模n成正比的時候，空間複雜度記作：O(n)

二維空間

當算法配置設定的空間是一個二維數組，并且集合的長度和寬度都與輸入規模n成正比的時候，空間複雜度記作：O(n^2)

遞歸空間

遞歸是一個比較特殊的場景，雖然遞歸代碼中并沒有顯式地聲明變量或者集合，但是計算機在執行程式的時候，會專門配置設定一塊記憶體空間，用來存儲

方法調用棧

，如果遞歸的深度為n，那麼空間複雜度為O(n)

方法調用棧包括進棧和出棧2個行為，具體會在後面的章節進行說明。

時間與空間的取舍

絕大多數的時候，時間複雜度更為重要一些，我們甯願多配置設定一些記憶體空間，也要提升算法的執行速度。

總結

• 什麼是算法

  在計算機領域，算法指一系列程式指令，用于處理特定的運算和邏輯問題。

  衡量算法優劣的主要标準就是時間複雜度和空間複雜度。

• 什麼是時間複雜度

  時間複雜度是對一個算法運作時間長短的量度，用大寫的O表示，記作：T(n)=O(f(n))

  常見的時間複雜度從低到高排序為：O(1) < O(logn) < O(n) < O(n^2) 等。

• 什麼是空間複雜度

  空間複雜度是對一個算法運作過程中臨時占用的存儲空間大小的量度，用大寫的O表示，記作：S(n)=O(f(n))

  常見的空間複雜度從低到高排序為：O(1) < O(n) < O(n^2)

  遞歸算法的空間複雜度和遞歸深度成正比。

  此外，說起空間複雜度，就必須要提到資料結構，那麼從下一節開始介紹常見的資料結構有哪些。