1. 時間復雜度轉化為空間復雜度

常用的降低時間復雜度的方法有遞歸、二分法、排序算法、動態規劃等，降低空間復雜度的核心思路就是，能用低復雜度的數據結構能解決問題，就千萬不要用高復雜度的數據結構。
?

在程序開發中，連接時間和空間的橋梁就是數據結構。對于一個開發任務，如果你能找到一種高效的數據組織方式，采用合理的數據結構的話，那就可以實現時間復雜度的再次降低。同樣的，這通常會增加數據的存儲量，也就是增加了空間復雜度。
?

轉化步驟的流程如下：

1. 暴力解法。在沒有任何時間、空間約束下，完成代碼任務的開發；
2. 無效操作處理。將代碼中的無效計算、無效存儲剔除，降低時間或空間復雜度；
3. 時空轉換。設計合理數據結構，完成時間復雜度向空間復雜度的轉移；

2. 轉化步驟

2.1 暴力求解

假設有任意多張面額為 2 元、3 元、7 元的貨幣，現要用它們湊出 100 元，求總共有多少種可能性。
?

第一步：先使用暴力解法，不受時間、空間約束完成代碼開發。

int count = 0;
for (int i = 0; i <= (100 / 7); i++) 
{for (int j = 0; j <= (100 / 3); j++) {for (int k = 0; k <= (100 / 2); k++) {if (i * 7 + j * 3 + k * 2 == 100) {count += 1;}}}
}

在這段代碼中，使用了 3 層的 for 循環。從結構上來看，是很顯然的 O( n3 ) 的時間復雜度。然而，仔細觀察就會發現，代碼中最內層的 for 循環是多余的。因為，當你確定了要用 i 張 7 元和 j 張 3 元時，只需要判斷用有限個 2 元能否湊出 100 - 7* i - 3* j 元就可以了。因此，代碼改寫如下：
?

2.2 剔除無效代碼

第二步：將代碼中的無效計算、無效存儲剔除。

int count = 0;
for (int i = 0; i <= (100 / 7); i++) 
{for (int j = 0; j <= (100 / 3); j++) {if ((100-i*7-j*3 >= 0)&&((100-i*7-j*3) % 2 == 0)) {count += 1;}}
}

經過改造后，代碼的結構由 3 層 for 循環，變成了 2 層 for 循環。很顯然，時間復雜度就變成了O(n2) 。這樣的代碼改造，就是利用了方法論中的步驟二，將代碼中的無效計算、無效存儲剔除，降低時間或空間復雜度。

2.3 時空轉化

查找出一個數組中，出現次數最多的那個元素的數值。例如，輸入數組 a = [1,2,3,4,5,5,6 ] 中，查找出現次數最多的數值。從數組中可以看出，只有 5 出現了 2 次，其余都是 1 次。顯然 5 出現的次數最多，則輸出 5。
?

第一種方法：
采用兩層的 for 循環完成計算。第一層循環，對數組每個元素遍歷。第二層循環，則是對第一層遍歷的數字，去遍歷計算其出現的次數。

def func():a = [1, 2, 3, 4, 5, 5, 6]b = []for i in range(len(a)):count_num = 0for j in range(len(a)):if a[i] == a[j]:count_num += 1b.append(count_num)print("b is {}".format(b))max_value = max(b)print("max_value is {}".format(max_value))max_value_index = b.index(max_value)print("max_value_index is {}".format(max_value_index))appera_max_value = a[max_value_index]print("appera_max_value is {}".format(appera_max_value))

兩層的 for 循環，很顯然時間復雜度就是 O(n2)。而且代碼中，幾乎沒有冗余的無效計算。如果還需要再去優化，就要考慮采用一些數據結構方面的手段，來把時間復雜度轉移到空間復雜度了。
?

這個問題能否通過一次 for 循環就找到答案呢？一個直觀的想法是，一次循環的過程中，我們同步記錄下每個元素出現的次數。最后，再通過查找次數最大的元素，就得到了結果。具體而言，定義一個 k-v 結構的字典，用來存放元素-出現次數的 k-v 關系。那么首先通過一次循環，將數組轉變為元素-出現次數的一個字典。接下來，再去遍歷一遍這個字典，找到出現次數最多的那個元素，就能找到最后的結果了。

def func2():a = [1, 2, 3, 4, 5, 5, 6]d = {}for i in a:if i not in d:d[i] = 1else:d[i] += 1print("init d is {}".format(d))max_value = max(d.values())print("max_value is {}".format(max_value))for k, v in d.items():if v == max_value:print("appera_max_value is {}".format(k))

我們來計算下這種方法的時空復雜度。代碼結構上，有兩個 for 循環。不過，這兩個循環不是嵌套關系，而是順序執行關系。其中，第一個循環實現了數組轉字典的過程，也就是 O(n) 的復雜度。第二個循環再次遍歷字典找到出現次數最多的那個元素，也是一個 O(n) 的時間復雜度。
?

因此，總體的時間復雜度為 O(n) + O(n)，就是 O(2n)，根據復雜度與具體的常系數無關的原則，也就是O(n)的復雜度。空間方面，由于定義了 k-v 字典，其字典元素的個數取決于輸入數組元素的個數。因此，空間復雜度增加為 O(n)。
?

這段代碼的開發，就是借鑒了方法論中的步驟三，通過采用更復雜、高效的數據結構，完成了時空轉移，提高了空間復雜度，讓時間復雜度再次降低。

總結

以上是生活随笔為你收集整理的数据结构（02）— 时间复杂度与空间复杂度转换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。