前面我說到了，咱們這個專欄的目標是想教會你利用數據結構的知識，建立算法思維，并完成代碼效率的優化。為了達到這個目標，在第一節課，我們先來講一講如何衡量程序運行的效率。 當你在大數據環境中開發代碼時，你一定遇到過程序執行好幾個小時、甚至好幾天的情況，或者是執行過程中電腦幾乎死機的情況： * 如果這個效率低下的系統是離線的，那么它會讓我們的開發周期、測試周期變得很長。 * 如果這個效率低下的系統是在線的，那么它隨時具有時間爆炸或者內存爆炸的可能性。 因此，衡量代碼的運行效率對于一個工程師而言，是一項非常重要的基本功。本課時我們就來學習程序運行效率相關的度量方法。 #### 復雜度是什么 **復雜度是衡量代碼運行效率的重要的度量因素**。在介紹復雜度之前，有必要先看一下復雜度和計算機實際任務處理效率的關系，從而了解降低復雜度的必要性。 計算機通過一個個程序去執行計算任務，也就是對輸入數據進行加工處理，并最終得到結果的過程。每個程序都是由代碼構成的。可見，編寫代碼的核心就是要完成計算。但對于同一個計算任務，不同計算方法得到結果的過程復雜程度是不一樣的，這對你實際的任務處理效率就有了非常大的影響。 舉個例子，你要在一個在線系統中實時處理數據。假設這個系統平均每分鐘會新增 300M 的數據量。如果你的代碼不能在 1 分鐘內完成對這 300M 數據的處理，那么這個系統就會發生時間爆炸和空間爆炸。表現就是，電腦執行越來越慢，直到死機。因此，我們需要講究合理的計算方法，去通過盡可能低復雜程度的代碼完成計算任務。 那提到降低復雜度，我們首先需要知道怎么衡量復雜度。而在實際衡量時，我們通常會圍繞以下2 個維度進行。**首先，這段代碼消耗的資源是什么**。一般而言，代碼執行過程中會消耗計算時間和計算空間，那需要衡量的就是時間復雜度和空間復雜度。 我舉一個實際生活中的例子。某個十字路口沒有建立立交橋時，所有車輛通過紅綠燈分批次行駛通過。當大量汽車同時過路口的時候，就會分別消耗大家的時間。但建了立交橋之后，所有車輛都可以同時通過了，因為立交橋的存在，等于是消耗了空間資源，來換取了時間資源。 **其次，這段代碼對于資源的消耗是多少**。我們不會關注這段代碼對于資源消耗的絕對量，因為不管是時間還是空間，它們的消耗程度都與輸入的數據量高度相關，輸入數據少時消耗自然就少。為了更客觀地衡量消耗程度，我們通常會關注時間或者空間消耗量與輸入數據量之間的關系。 好，現在我們已經了解了衡量復雜度的兩個緯度，那應該如何去計算復雜度呢？ **復雜度是一個關于輸入數據量 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(n2)+O(n) 和 O(n2) 表示的是同樣的復雜度。具體分析一下就是，O(n2)+O(n) = O(n2+n)。隨著 n 越來越大，二階多項式的變化率是要比一階多項式更大的。因此，只需要通過更大變化率的二階多項式來表征復雜度就可以了。 值得一提的是，O(1) 也是表示一個特殊復雜度，含義為某個任務通過有限可數的資源即可完成。此處有限可數的具體意義是，與輸入數據量 n 無關。 例如，你的代碼處理 10 條數據需要消耗 5 個單位的時間資源，3 個單位的空間資源。處理 1000 條數據，還是只需要消耗 5 個單位的時間資源，3 個單位的空間資源。那么就能發現資源消耗與輸入數據量無關，就是 O(1) 的復雜度。 為了方便你理解不同計算方法對復雜度的影響，我們來看一個代碼任務：對于輸入的數組，輸出與之逆序的數組。例如，輸入 a=[1,2,3,4,5]，輸出 [5,4,3,2,1]。 先看方法一，建立并初始化數組 b，得到一個與輸入數組等長的全零數組。通過一個 for 循環，從左到右將 a 數組的元素，從右到左地賦值到 b 數組中，最后輸出數組 b 得到結果。  代碼如下： ``` public void s1_1() { int a[] = { 1, 2, 3, 4, 5 }; int b[] = new int[5]; for (int i = 0; i < a.length; i++) { b[i] = a[i]; } for (int i = 0; i < a.length; i++) { b[a.length - i - 1] = a[i]; } System.out.println(Arrays.toString(b)); } ``` 這段代碼的輸入數據是 a，數據量就等于數組 a 的長度。代碼中有兩個 for 循環，作用分別是給b 數組初始化和賦值，其執行次數都與輸入數據量相等。因此，代碼的時間復雜度就是 O(n)+O(n)，也就是 O(n)。 空間方面主要體現在計算過程中，對于存儲資源的消耗情況。上面這段代碼中，我們定義了一個新的數組 b，它與輸入數組 a 的長度相等。因此，空間復雜度就是 O(n)。 接著我們看一下第二種編碼方法，它定義了緩存變量 tmp，接著通過一個 for 循環，從 0 遍歷到a 數組長度的一半（即 len(a)/2）。每次遍歷執行的是什么內容？就是交換首尾對應的元素。最后打印數組 a，得到結果。  代碼如下： ``` public void s1_2() { int a[] = { 1, 2, 3, 4, 5 }; int tmp = 0; for (int i = 0; i < (a.length / 2); i++) { tmp = a[i]; a[i] = a[a.length - i - 1]; a[a.length - i - 1] = tmp; } System.out.println(Arrays.toString(a)); } ``` 這段代碼包含了一個 for 循環，執行的次數是數組長度的一半，時間復雜度變成了 O(n/2)。根據復雜度與具體的常系數無關的性質，這段代碼的時間復雜度也就是 O(n)。 空間方面，我們定義了一個 tmp 變量，它與數組長度無關。也就是說，輸入是 5 個元素的數組，需要一個 tmp 變量；輸入是 50 個元素的數組，依然只需要一個 tmp 變量。因此，空間復雜度與輸入數組長度無關，即 O(1)。 可見，對于同一個問題，采用不同的編碼方法，對時間和空間的消耗是有可能不一樣的。因此，工程師在寫代碼的時候，一方面要完成任務目標；另一方面，也需要考慮時間復雜度和空間復雜度，以求用盡可能少的時間損耗和盡可能少的空間損耗去完成任務。 * [ ] 時間復雜度與代碼結構的關系 好了，通過前面的內容，相信你已經對時間復雜度和空間復雜度有了很好的理解。從本質來看，時間復雜度與代碼的結構有著非常緊密的關系；而空間復雜度與數據結構的設計有關，關于這一點我們會在下一講進行詳細闡述。接下來我先來系統地講一下時間復雜度和代碼結構的關系。 代碼的時間復雜度，與代碼的結構有非常強的關系，我們一起來看一些具體的例子。 例 1，定義了一個數組 a = [1, 4, 3]，查找數組 a 中的最大值，代碼如下： ``` public void s1_3() { int a[] = { 1, 4, 3 }; int max_val = -1; for (int i = 0; i < a.length; i++) { if (a[i] > max_val) { max_val = a[i]; } } System.out.println(max_val); } ``` 這個例子比較簡單，實現方法就是，暫存當前最大值并把所有元素遍歷一遍即可。因為代碼的結構上需要使用一個 for 循環，對數組所有元素處理一遍，所以時間復雜度為 O(n)。 例2，下面的代碼定義了一個數組 a = [1, 3, 4, 3, 4, 1, 3]，并會在這個數組中查找出現次數最多的那個數字： ``` public void s1_4() { int a[] = { 1, 3, 4, 3, 4, 1, 3 }; int val_max = -1; int time_max = 0; int time_tmp = 0; for (int i = 0; i < a.length; i++) { time_tmp = 0; for (int j = 0; j < a.length; j++) { if (a[i] == a[j]) { time_tmp += 1; } if (time_tmp > time_max) { time_max = time_tmp; val_max = a[i]; } } } System.out.println(val_max); } ``` 這段代碼中，我們采用了雙層循環的方式計算：第一層循環，我們對數組中的每個元素進行遍歷；第二層循環，對于每個元素計算出現的次數，并且通過當前元素次數 time_tmp 和全局最大次數變量 time_max 的大小關系，持續保存出現次數最多的那個元素及其出現次數。由于是雙層循環，這段代碼在時間方面的消耗就是 n*n 的復雜度，也就是 O(n2)。 在這里，我們給出一些經驗性的結論： * 一個順序結構的代碼，時間復雜度是 O(1)。 * 二分查找，或者更通用地說是采用分而治之的二分策略，時間復雜度都是 O(logn)。這個我們會在后續課程講到。 * 一個簡單的 for 循環，時間復雜度是 O(n)。 * 兩個順序執行的 for 循環，時間復雜度是 O(n)+O(n)=O(2n)，其實也是 O(n)。 * 兩個嵌套的 for 循環，時間復雜度是 O(n2)。 有了這些基本的結論，再去分析代碼的時間復雜度將會輕而易舉。 * [ ] 降低時間復雜度的必要性 很多新手的工程師，對降低時間復雜度并沒有那么強的意識。這主要是在學校或者實驗室中，參加的課程作業或者科研項目，普遍都不是實時的、在線的工程環境。 實際的在線環境中，用戶的訪問請求可以看作一個流式數據。假設這個數據流中，每個訪問的平均時間間隔是 t。如果你的代碼無法在 t 時間內處理完單次的訪問請求，那么這個系統就會一波未平一波又起，最終被大量積壓的任務給壓垮。這就要求工程師必須通過優化代碼、優化數據結構，來降低時間復雜度。 為了更好理解，我們來看一些數據。假設某個計算任務需要處理 10萬 條數據。你編寫的代碼： * 如果是 O(n2) 的時間復雜度，那么計算的次數就大概是 100 億次左右。 * 如果是 O(n)，那么計算的次數就是 10萬 次左右。 * 如果這個工程師再厲害一些，能在 O(log n) 的復雜度下完成任務，那么計算的次數就是 17 次左右（log 100000 = 16.61，計算機通常是二分法，這里的對數可以以 2 為底去估計）。 數字是不是一下子變得很懸殊？通常在小數據集上，時間復雜度的降低在絕對處理時間上沒有太多體現。但在當今的大數據環境下，時間復雜度的優化將會帶來巨大的系統收益。而這是優秀工程師必須具備的工程開發基本意識。 #### 總結 OK，今天的內容到這兒就結束了。相信你對復雜度的概念有了進一步的認識。 復雜度通常包括時間復雜度和空間復雜度。在具體計算復雜度時需要注意以下幾點。 它與具體的常系數無關，O(n) 和 O(2n) 表示的是同樣的復雜度。 復雜度相加的時候，選擇高者作為結果，也就是說 O(n2)+O(n) 和 O(n2) 表示的是同樣的復雜度。 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++) { } } } ``` 關于復雜度的評估，需要你深入理解本節課的知識點。最后，你工作中有遇到過關于計算復雜度的哪些實際問題嗎？你又是如何解決的？歡迎你在留言區和我分享。