文章目錄 - 一、代碼效率優化方法論
- 二、将“昂貴”的時間複雜度轉換成“廉價”的空間複雜度
一、代碼效率優化方法論
熟練應用資料結構的知識，建立算法思維，完成代碼效率的優化。
複雜度是衡量代碼運作效率的重要度量因素
- 計算機通過一個個程式去執行計算任務，也就是對輸入資料進行加工處理，并最終得到結果的過程；
- 每個程式都是由代碼構成的，編寫代碼的核心就是要完成計算；
- 但對于同一個計算任務，不同計算方法得到結果的過程複雜程度是不一樣的，這對實際的任務處理效率就有了非常大的影響；
- 在實際應用中需要講究合理的計算方法，去通過盡可能低複雜程度的代碼完成計算任務；
那提到降低複雜度，我們首先需要知道怎麼衡量複雜度。
代碼執行過程中會消耗計算時間和計算空間，那需要衡量的就是時間複雜度和空間複雜度。
不管是時間還是空間，它們的消耗程度都與輸入的資料量高度相關，輸入資料少時消耗自然就少。為了更客觀地衡量消耗程度，我們通常會關注時間或者空間消耗量與輸入資料量之間的關系。
複雜度是一個關于輸入資料量 n 的函數。假設你的代碼複雜度是 f(n)，那麼就用個大寫字母 O 和括号，把 f(n) 括起來就可以了，即 O(f(n))。例如，O(n) 表示的是，複雜度與計算執行個體的個數 n 線性相關；O(logn) 表示的是，複雜度與計算執行個體的個數 n 對數相關。
通常，複雜度的計算方法遵循以下幾個原則：
- 複雜度與具體的常系數無關：例如 O(n) 和 O(2n) 表示的是同樣的複雜度。我們詳細分析下，O(2n) 等于 O(n+n)，也等于 O(n) + O(n)。也就是說，一段 O(n) 複雜度的代碼隻是先後執行兩遍 O(n)，其複雜度是一緻的。
- 多項式級的複雜度相加的時候，選擇高者作為結果：例如 O(n²)+O(n) 和 O(n²) 表示的是同樣的複雜度。具體分析一下就是，O(n²)+O(n) = O(n²+n)。随着 n 越來越大，二階多項式的變化率是要比一階多項式更大的。是以，隻需要通過更大變化率的二階多項式來表征複雜度即可。
- O(1) 表示一個特殊複雜度：含義為某個任務通過有限可數的資源即可完成。此處有限可數的具體意義是，與輸入資料量 n 無關。
一些經驗性的結論：
- 一個順序結構的代碼，時間複雜度是 O(1)；
- 二分查找，或者更通用地說是采用分而治之的二分政策，時間複雜度都是 O(logn)；
- 一個簡單的 for 循環，時間複雜度是 O(n)；
- 兩個順序執行的 for 循環，時間複雜度是 O(n)+O(n)=O(2n)，其實也是 O(n)；
- 兩個嵌套的 for 循環，時間複雜度是 O(n²)；
降低時間複雜度的必要性：
假設某個計算任務需要處理 10 萬 條資料，你編寫的代碼：
- 如果是 O(n²) 的時間複雜度，那麼計算的次數就大概是 100 億次左右；
- 如果是 O(n)，那麼計算的次數就是 10 萬 次左右；
- 如果能寫出高效算法，在 O(log n) 的複雜度下完成任務，那麼計算的次數就是 17 次左右（log 100000 = 16.61，計算機通常是二分法，這裡的對數可以以 2 為底去估計）
通常在小資料集上，時間複雜度的降低在絕對處理時間上沒有太多展現。但在當今的大資料環境下，時間複雜度的優化将會帶來巨大的系統收益。而這是優秀工程師必須具備的工程開發基本意識。
複雜度通常包括時間複雜度和空間複雜度，在具體計算複雜度時需要注意以下幾點：
- 它與具體的常系數無關，O(n) 和 O(2n) 表示的是同樣的複雜度；
- 複雜度相加的時候，選擇高次項作為結果，也就是說 O(n²)+O(n) 和 O(n²) 表示的是同樣的複雜度；
- O(1) 也是表示一個特殊複雜度，即任務與算例個數 n 無關；
- 時間複雜度與代碼的結構設計高度相關；
- 空間複雜度與代碼中資料結構的選擇高度相關；
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
for (k = 0; k < n; k++) {
}
for (m = 0; m < n; m++) {
}
}
}
時間複雜度為O(n^3) 複制
二、将“昂貴”的時間複雜度轉換成“廉價”的空間複雜度
代碼效率優化就是要将可行解提高到更優解，最終目标是：要采用盡可能低的時間複雜度和空間複雜度，去完成一段代碼的開發。
代碼效率的瓶頸可能發生在時間或者空間兩個方面。如果是缺少計算空間，花錢買伺服器就可以了，這是個花錢就能解決的問題；相反，如果是缺少計算時間，隻能投入寶貴的人生去跑程式。即使你有再多的錢、再多的伺服器，也是毫無用處。相比于空間複雜度，時間複雜度的降低就顯得更加重要了。是以，可以發現這樣的結論：相對而言，空間是廉價的，而時間是昂貴的。
假定在不限制時間、也不限制空間的情況下，你可以完成某個任務的代碼的開發。這就是通常我們所說的暴力解法，更是程式優化的起點。
例如，如果要在 100 以内的正整數中，找到同時滿足以下兩個條件的最小數字：
- 除 5 餘 2
- 除 7 餘 3
暴力的解法就是，從 1 開始到 100，每個數字都做一次判斷。如果這個數字滿足了上述兩個條件，則傳回結果。這是一種不計較任何時間複雜度或空間複雜度的、最直覺的暴力解法。
當你有了最暴力的解法後，就需要用上一講的方法評估目前暴力解法的複雜度了。如果複雜度比較低或者可以接受，那自然萬事大吉。可如果暴力解法複雜度比較高的話，那就要考慮采用程式優化的方法去降低複雜度了。
為了降低複雜度，一個直覺的思路是：梳理程式，看其流程中是否有無效的計算或者無效的存儲。
我們需要從時間複雜度和空間複雜度兩個次元來考慮。常用的降低時間複雜度的方法有遞歸、二分法、排序算法、動态規劃等；而降低空間複雜度的方法，就要圍繞資料結構做文章了。
降低空間複雜度的核心思路就是：能用低複雜度的資料結構能解決問題，就千萬不要用高複雜度的資料結構。
在程式開發中，連接配接時間和空間的橋梁就是資料結構。對于一個開發任務，如果你能找到一種高效的資料組織方式，采用合理的資料結構的話，那就可以實作時間複雜度的再次降低。同樣的，這通常會增加資料的存儲量，也就是增加了空間複雜度。
程式優化的核心的思路如下：
- 第一步，暴力解法。在沒有任何時間、空間限制下，完成代碼任務的開發。
- 第二步，處理無效操作。将代碼中的無效計算、無效存儲剔除，降低時間或空間複雜度。
- 第三步，時空轉換。設計合理資料結構，完成時間複雜度向空間複雜度的轉移，以空間換時間。
舉例如下：
假設有任意多張面額為 2 元、3 元、7 元的貨币，現要用它們湊出 100 元，求總共有多少種可能性。
count = 0
for i in range(0, 100 // 7 + 1):
for j in range(0, 100 // 3 + 1):
for k in range(0, 100 // 2 + 1):
if i * 7 + j * 3 + k * 2 == 100:
count += 1
print(f'總共有 {count} 種可能性')
運作結果如下：
總共有 134 種可能性 複制
在這段代碼中，使用了 3 層的 for 循環。從結構上來看，很顯然是 O( n³ ) 的時間複雜度。然而，仔細觀察就會發現，代碼中最内層的 for 循環是多餘的。因為，當你确定了要用 i 張 7 元和 j 張 3 元時，隻需要判斷用有限個 2 元能否湊出 100 - 7* i - 3* j 元即可，代碼改寫如下：
count = 0
for i in range(0, 100 // 7 + 1):
for j in range(0, 100 // 3 + 1):
if (100 - 7 * i - 3 * j) >= 0 and (100 - i * 7 - j * 3) % 2 == 0:
count += 1
print(f'總共有 {count} 種可能性')
運作結果如下：
總共有 134 種可能性 複制
經過優化後，代碼的結構由 3 層 for 循環，變成了 2 層 for 循環。很顯然，時間複雜度就變成了O(n²) 。這樣的代碼改造，就是利用了方法論中的步驟二，将代碼中的無效計算、無效存儲剔除，降低時間或空間複雜度。
查找出一個數組中，出現次數最多的那個元素的數值。例如，輸入 a = [1,2,3,4,6,5,6,6 ] 中，查找出現次數最多的數值。從數組中可以看出，隻有 6 出現了 3 次，其餘都是 1 次。顯然 6 出現的次數最多，結果輸出 6。
a = [1, 2, 3, 4, 6, 5, 6, 6]
val_max, time_max = -1, 0
for i in range(0, len(a)):
time_tmp = 0
for j in range(0, len(a)):
if a[i] == a[j]:
time_tmp += 1
# 出現次數大于之前最大的 重新複制 value 和出現次數
if time_tmp > time_max:
time_max = time_tmp
val_max = a[i]
print(val_max, time_tmp)
運作結果如下：
6 3 複制
采用兩層的 for 循環完成計算， 很顯然時間複雜度是 O(n²)。第一層循環，對數組每個元素周遊。第二層循環，則是對第一層周遊的數字，去周遊計算其出現的次數。這樣，全局再同時緩存一個出現次數最多的元素及其次數就可以實作。代碼中，幾乎沒有備援的無效計算。如果還需要再去優化，就要考慮采用一些資料結構方面的手段，來把時間複雜度轉移到空間複雜度了。
這個問題能否通過一次 for 循環就找到答案呢？一個直覺的想法是，一次循環的過程中，我們同步記錄下每個元素出現的次數。最後，再通過查找次數最大的元素，就得到了結果。
具體而言，定義一個 k-v 結構的字典，用來存放元素-出現次數的 k-v 關系。那麼首先通過一次循環，将數組轉變為元素-出現次數的一個字典。接下來，再去周遊一遍這個字典，找到出現次數最多的那個元素，就能找到最後的結果了。
a = [1, 2, 3, 4, 6, 5, 6, 6]
d = {}
for i in a:
if i in d.keys():
d[i] += 1
else:
d[i] = 1
print(d)
for k, v in d.items():
if v > temp_max:
time_max = v
print(temp_max)
val_max = k
print(val_max, time_max)
運作結果如下：
6 3 複制
來計算下這種方法的時空複雜度。代碼結構上，有兩個 for 循環。不過，這兩個循環不是嵌套關系，而是順序執行關系。其中，第一個循環實作了數組轉字典的過程，也就是 O(n) 的複雜度。第二個循環再次周遊字典找到出現次數最多的那個元素，也是一個 O(n) 的時間複雜度。
是以，總體的時間複雜度為 O(n) + O(n)，就是 O(2n)，根據複雜度與具體的常系數無關的原則，也就是O(n) 的複雜度。空間方面，由于定義了 k-v 字典，其字典元素的個數取決于輸入數組元素的個數。是以，空間複雜度增加為 O(n)。
這段代碼的開發，就是借鑒了方法論中的步驟三，通過采用更複雜、高效的資料結構，完成了時空轉移，提高了空間複雜度，讓時間複雜度再次降低。
降低複雜度，優化程式的核心的思路如下：
- 第一步，暴力解法。在沒有任何時間、空間限制下，完成代碼任務的開發。
- 第二步，處理無效操作。将代碼中的無效計算、無效存儲剔除，降低時間或空間複雜度。
- 第三步，時空轉換。設計合理資料結構，完成時間複雜度向空間複雜度的轉移，以空間換時間。
作者：葉庭雲
CSDN：https://yetingyun.blog.csdn.net/