為什么所有程序員都該學(xué)好數(shù)據(jù)結(jié)構(gòu)與算法？在你的工作中你會(huì)發(fā)現(xiàn)，利用數(shù)據(jù)結(jié)構(gòu)的知識，建立算法思維，更好完成代碼效率的優(yōu)化。我們先來講一講如何衡量程序運(yùn)行的效率。
當(dāng)你在大數(shù)據(jù)環(huán)境中開發(fā)代碼時(shí)，你一定遇到過程序執(zhí)行好幾個(gè)小時(shí)、甚至好幾天的情況，或者是執(zhí)行過程中電腦幾乎死機(jī)的情況：
如果這個(gè)效率低下的系統(tǒng)是離線的，那么它會(huì)讓我們的開發(fā)周期、測試周期變得很長。如果這個(gè)效率低下的系統(tǒng)是在線的，那么它隨時(shí)具有時(shí)間爆炸或者內(nèi)存爆炸的可能性。因此，衡量代碼的運(yùn)行效率對于一個(gè)工程師而言，是一項(xiàng)非常重要的基本功，我們就來學(xué)習(xí)程序運(yùn)行效率相關(guān)的度量方法。
復(fù)雜度是什么復(fù)雜度是衡量代碼運(yùn)行效率的重要的度量因素。在介紹復(fù)雜度之前，有必要先看一下復(fù)雜度和計(jì)算機(jī)實(shí)際任務(wù)處理效率的關(guān)系，從而了解降低復(fù)雜度的必要性。
計(jì)算機(jī)通過一個(gè)個(gè)程序去執(zhí)行計(jì)算任務(wù)，也就是對輸入數(shù)據(jù)進(jìn)行加工處理，并最終得到結(jié)果的過程。每個(gè)程序都是由代碼構(gòu)成的?？梢?，編寫代碼的核心就是要完成計(jì)算。但對于同一個(gè)計(jì)算任務(wù)，不同計(jì)算方法得到結(jié)果的過程復(fù)雜程度是不一樣的，這對你實(shí)際的任務(wù)處理效率就有了非常大的影響。
舉個(gè)例子，你要在一個(gè)在線系統(tǒng)中實(shí)時(shí)處理數(shù)據(jù)。假設(shè)這個(gè)系統(tǒng)平均每分鐘會(huì)新增 300M 的數(shù)據(jù)量。如果你的代碼不能在 1 分鐘內(nèi)完成對這 300M 數(shù)據(jù)的處理，那么這個(gè)系統(tǒng)就會(huì)發(fā)生時(shí)間爆炸和空間爆炸。表現(xiàn)就是，電腦執(zhí)行越來越慢，直到死機(jī)。因此，我們需要講究合理的計(jì)算方法，去通過盡可能低復(fù)雜程度的代碼完成計(jì)算任務(wù)。
那提到降低復(fù)雜度，我們首先需要知道怎么衡量復(fù)雜度。而在實(shí)際衡量時(shí)，我們通常會(huì)圍繞以下2 個(gè)維度進(jìn)行。首先，這段代碼消耗的資源是什么。一般而言，代碼執(zhí)行過程中會(huì)消耗計(jì)算時(shí)間和計(jì)算空間，那需要衡量的就是時(shí)間復(fù)雜度和空間復(fù)雜度。
我舉一個(gè)實(shí)際生活中的例子。某個(gè)十字路口沒有建立立交橋時(shí)，所有車輛通過紅綠燈分批次行駛通過。當(dāng)大量汽車同時(shí)過路口的時(shí)候，就會(huì)分別消耗大家的時(shí)間。但建了立交橋之后，所有車輛都可以同時(shí)通過了，因?yàn)榱⒔粯虻拇嬖?，等于是消耗了空間資源，來換取了時(shí)間資源。
其次，這段代碼對于資源的消耗是多少。我們不會(huì)關(guān)注這段代碼對于資源消耗的絕對量，因?yàn)椴还苁菚r(shí)間還是空間，它們的消耗程度都與輸入的數(shù)據(jù)量高度相關(guān)，輸入數(shù)據(jù)少時(shí)消耗自然就少。為了更客觀地衡量消耗程度，我們通常會(huì)關(guān)注時(shí)間或者空間消耗量與輸入數(shù)據(jù)量之間的關(guān)系。
好，現(xiàn)在我們已經(jīng)了解了衡量復(fù)雜度的兩個(gè)緯度，那應(yīng)該如何去計(jì)算復(fù)雜度呢？
復(fù)雜度是一個(gè)關(guān)于輸入數(shù)據(jù)量 n 的函數(shù)。假設(shè)你的代碼復(fù)雜度是 f(n)，那么就用個(gè)大寫字母 O 和括號，把 f(n) 括起來就可以了，即 O(f(n))。例如，O(n) 表示的是，復(fù)雜度與計(jì)算實(shí)例的個(gè)數(shù) n 線性相關(guān)；O(logn) 表示的是，復(fù)雜度與計(jì)算實(shí)例的個(gè)數(shù) n 對數(shù)相關(guān)。
通常，復(fù)雜度的計(jì)算方法遵循以下幾個(gè)原則：
首先，復(fù)雜度與具體的常系數(shù)無關(guān)，例如 O(n) 和 O(2n) 表示的是同樣的復(fù)雜度。我們詳細(xì)分析下，O(2n) 等于 O(n+n)，也等于 O(n) + O(n)。也就是說，一段 O(n) 復(fù)雜度的代碼只是先后執(zhí)行兩遍 O(n)，其復(fù)雜度是一致的。其次，多項(xiàng)式級的復(fù)雜度相加的時(shí)候，選擇高者作為結(jié)果，例如 O(n2)+O(n) 和 O(n2) 表示的是同樣的復(fù)雜度。具體分析一下就是，O(n2)+O(n) = O(n2+n)。隨著 n 越來越大，二階多項(xiàng)式的變化率是要比一階多項(xiàng)式更大的。因此，只需要通過更大變化率的二階多項(xiàng)式來表征復(fù)雜度就可以了。值得一提的是，O(1) 也是表示一個(gè)特殊復(fù)雜度，含義為某個(gè)任務(wù)通過有限可數(shù)的資源即可完成。此處有限可數(shù)的具體意義是，與輸入數(shù)據(jù)量 n 無關(guān)。
例如，你的代碼處理 10 條數(shù)據(jù)需要消耗 5 個(gè)單位的時(shí)間資源，3 個(gè)單位的空間資源。處理 1000 條數(shù)據(jù)，還是只需要消耗 5 個(gè)單位的時(shí)間資源，3 個(gè)單位的空間資源。那么就能發(fā)現(xiàn)資源消耗與輸入數(shù)據(jù)量無關(guān)，就是 O(1) 的復(fù)雜度。
為了方便你理解不同計(jì)算方法對復(fù)雜度的影響，我們來看一個(gè)代碼任務(wù)：對于輸入的數(shù)組，輸出與之逆序的數(shù)組。例如，輸入 a=[1,2,3,4,5]，輸出 [5,4,3,2,1]。
先看方法一，建立并初始化數(shù)組 b，得到一個(gè)與輸入數(shù)組等長的全零數(shù)組。通過一個(gè) for 循環(huán)，從左到右將 a 數(shù)組的元素，從右到左地賦值到 b 數(shù)組中，最后輸出數(shù)組 b 得到結(jié)果。
代碼如下：
這段代碼的輸入數(shù)據(jù)是 a，數(shù)據(jù)量就等于數(shù)組 a 的長度。代碼中有兩個(gè) for 循環(huán)，作用分別是給b 數(shù)組初始化和賦值，其執(zhí)行次數(shù)都與輸入數(shù)據(jù)量相等。因此，代碼的時(shí)間復(fù)雜度就是 O(n)+O(n)，也就是 O(n)。
空間方面主要體現(xiàn)在計(jì)算過程中，對于存儲(chǔ)資源的消耗情況。上面這段代碼中，我們定義了一個(gè)新的數(shù)組 b，它與輸入數(shù)組 a 的長度相等。因此，空間復(fù)雜度就是 O(n)。
接著我們看一下第二種編碼方法，它定義了緩存變量 tmp，接著通過一個(gè) for 循環(huán)，從 0 遍歷到a 數(shù)組長度的一半（即 len(a)/2）。每次遍歷執(zhí)行的是什么內(nèi)容？就是交換首尾對應(yīng)的元素。最后打印數(shù)組 a，得到結(jié)果。
代碼如下：
這段代碼包含了一個(gè) for 循環(huán)，執(zhí)行的次數(shù)是數(shù)組長度的一半，時(shí)間復(fù)雜度變成了 O(n/2)。根據(jù)復(fù)雜度與具體的常系數(shù)無關(guān)的性質(zhì)，這段代碼的時(shí)間復(fù)雜度也就是 O(n)。
空間方面，我們定義了一個(gè) tmp 變量，它與數(shù)組長度無關(guān)。也就是說，輸入是 5 個(gè)元素的數(shù)組，需要一個(gè) tmp 變量；輸入是 50 個(gè)元素的數(shù)組，依然只需要一個(gè) tmp 變量。因此，空間復(fù)雜度與輸入數(shù)組長度無關(guān)，即 O(1)。
可見，對于同一個(gè)問題，采用不同的編碼方法，對時(shí)間和空間的消耗是有可能不一樣的。因此，工程師在寫代碼的時(shí)候，一方面要完成任務(wù)目標(biāo)；另一方面，也需要考慮時(shí)間復(fù)雜度和空間復(fù)雜度，以求用盡可能少的時(shí)間損耗和盡可能少的空間損耗去完成任務(wù)。
時(shí)間復(fù)雜度與代碼結(jié)構(gòu)的關(guān)系好了，通過前面的內(nèi)容，相信你已經(jīng)對時(shí)間復(fù)雜度和空間復(fù)雜度有了很好的理解。從本質(zhì)來看，時(shí)間復(fù)雜度與代碼的結(jié)構(gòu)有著非常緊密的關(guān)系；而空間復(fù)雜度與數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)有關(guān)，關(guān)于這一點(diǎn)我們會(huì)在下一講進(jìn)行詳細(xì)闡述。接下來我先來系統(tǒng)地講一下時(shí)間復(fù)雜度和代碼結(jié)構(gòu)的關(guān)系。
代碼的時(shí)間復(fù)雜度，與代碼的結(jié)構(gòu)有非常強(qiáng)的關(guān)系，我們一起來看一些具體的例子。
例 1，定義了一個(gè)數(shù)組 a = [1, 4, 3]，查找數(shù)組 a 中的最大值，代碼如下：
這個(gè)例子比較簡單，實(shí)現(xiàn)方法就是，暫存當(dāng)前最大值并把所有元素遍歷一遍即可。因?yàn)榇a的結(jié)構(gòu)上需要使用一個(gè) for 循環(huán)，對數(shù)組所有元素處理一遍，所以時(shí)間復(fù)雜度為 O(n)。
例2，下面的代碼定義了一個(gè)數(shù)組 a = [1, 3, 4, 3, 4, 1, 3]，并會(huì)在這個(gè)數(shù)組中查找出現(xiàn)次數(shù)最多的那個(gè)數(shù)字：
這段代碼中，我們采用了雙層循環(huán)的方式計(jì)算：第一層循環(huán)，我們對數(shù)組中的每個(gè)元素進(jìn)行遍歷；第二層循環(huán)，對于每個(gè)元素計(jì)算出現(xiàn)的次數(shù)，并且通過當(dāng)前元素次數(shù) time_tmp 和全局最大次數(shù)變量 time_max 的大小關(guān)系，持續(xù)保存出現(xiàn)次數(shù)最多的那個(gè)元素及其出現(xiàn)次數(shù)。由于是雙層循環(huán)，這段代碼在時(shí)間方面的消耗就是 n*n 的復(fù)雜度，也就是 O(n2)。
在這里，我們給出一些經(jīng)驗(yàn)性的結(jié)論：
一個(gè)順序結(jié)構(gòu)的代碼，時(shí)間復(fù)雜度是 O(1)。二分查找，或者更通用地說是采用分而治之的二分策略，時(shí)間復(fù)雜度都是 O(logn)。這個(gè)我們會(huì)在后續(xù)課程講到。一個(gè)簡單的 for 循環(huán)，時(shí)間復(fù)雜度是 O(n)。兩個(gè)順序執(zhí)行的 for 循環(huán)，時(shí)間復(fù)雜度是 O(n)+O(n)=O(2n)，其實(shí)也是 O(n)。兩個(gè)嵌套的 for 循環(huán)，時(shí)間復(fù)雜度是 O(n2)。有了這些基本的結(jié)論，再去分析代碼的時(shí)間復(fù)雜度將會(huì)輕而易舉。
降低時(shí)間復(fù)雜度的必要性很多新手的工程師，對降低時(shí)間復(fù)雜度并沒有那么強(qiáng)的意識。這主要是在學(xué)?；蛘邔?shí)驗(yàn)室中，參加的課程作業(yè)或者科研項(xiàng)目，普遍都不是實(shí)時(shí)的、在線的工程環(huán)境。
實(shí)際的在線環(huán)境中，用戶的訪問請求可以看作一個(gè)流式數(shù)據(jù)。假設(shè)這個(gè)數(shù)據(jù)流中，每個(gè)訪問的平均時(shí)間間隔是 t。如果你的代碼無法在 t 時(shí)間內(nèi)處理完單次的訪問請求，那么這個(gè)系統(tǒng)就會(huì)一波未平一波又起，最終被大量積壓的任務(wù)給壓垮。這就要求工程師必須通過優(yōu)化代碼、優(yōu)化數(shù)據(jù)結(jié)構(gòu)，來降低時(shí)間復(fù)雜度。
為了更好理解，我們來看一些數(shù)據(jù)。假設(shè)某個(gè)計(jì)算任務(wù)需要處理 10萬 條數(shù)據(jù)。你編寫的代碼：
如果是 O(n2) 的時(shí)間復(fù)雜度，那么計(jì)算的次數(shù)就大概是 100 億次左右。如果是 O(n)，那么計(jì)算的次數(shù)就是 10萬 次左右。如果這個(gè)工程師再厲害一些，能在 O(log n) 的復(fù)雜度下完成任務(wù)，那么計(jì)算的次數(shù)就是 17 次左右（log 100000 = 16.61，計(jì)算機(jī)通常是二分法，這里的對數(shù)可以以 2 為底去估計(jì)）。數(shù)字是不是一下子變得很懸殊？通常在小數(shù)據(jù)集上，時(shí)間復(fù)雜度的降低在絕對處理時(shí)間上沒有太多體現(xiàn)。但在當(dāng)今的大數(shù)據(jù)環(huán)境下，時(shí)間復(fù)雜度的優(yōu)化將會(huì)帶來巨大的系統(tǒng)收益。而這是優(yōu)秀工程師必須具備的工程開發(fā)基本意識。
總結(jié)OK，今天的內(nèi)容到這兒就結(jié)束了。相信你對復(fù)雜度的概念有了進(jìn)一步的認(rèn)識。
復(fù)雜度通常包括時(shí)間復(fù)雜度和空間復(fù)雜度。在具體計(jì)算復(fù)雜度時(shí)需要注意以下幾點(diǎn)。
它與具體的常系數(shù)無關(guān)，O(n) 和 O(2n) 表示的是同樣的復(fù)雜度。復(fù)雜度相加的時(shí)候，選擇高者作為結(jié)果，也就是說 O(n2)+O(n) 和 O(n2) 表示的是同樣的復(fù)雜度。O(1) 也是表示一個(gè)特殊復(fù)雜度，即任務(wù)與算例個(gè)數(shù) n 無關(guān)。復(fù)雜度細(xì)分為時(shí)間復(fù)雜度和空間復(fù)雜度，其中時(shí)間復(fù)雜度與代碼的結(jié)構(gòu)設(shè)計(jì)高度相關(guān)；空間復(fù)雜度與代碼中數(shù)據(jù)結(jié)構(gòu)的選擇高度相關(guān)。會(huì)計(jì)算一段代碼的時(shí)間復(fù)雜度和空間復(fù)雜度，是工程師的基本功。這項(xiàng)技能你在實(shí)際工作中一定會(huì)用到，甚至在參加互聯(lián)網(wǎng)公司面試的時(shí)候，也是面試中的必考內(nèi)容。
以上內(nèi)容，來自拉勾教育的新專欄「重學(xué)數(shù)據(jù)結(jié)構(gòu)與算法」，這個(gè)專欄會(huì)從方法論、基礎(chǔ)知識、真題演練、面試技巧這四個(gè)方面，帶你搞定數(shù)據(jù)結(jié)構(gòu)與算法的知識，為你提供成為優(yōu)秀工程師的完整路徑。
