上一篇--JavaScript算法之複雜度分析文章中介紹了複雜度的分析，相信小伙伴們對常見代碼的時間或者空間複雜度肯定能分析出來了。

思考測試

話不多說，出個題目考考大家，分析下面代碼的時間複雜度(ps: 雖然說並不會這麼寫)

function find(n, x, arr) { let ind = -1; for (let i = 0; i < n; i++) { if (arr[i] === x) ind = i; } return ind; }

上面函數的功能就是查找一個變量x 是否在數組arr 中，如果在的話，返回所在的位置，否則就返回-1。通過上一節的學習分析，這個函數的時間複雜度就很容易知道了，為O(n)。

接下來，稍微優化下這個find函數，如果查找到目標的話，就沒必要再往後查找了。

請分析下優化後函數的時間複雜度：

function find(n, x, arr) { let ind = -1; for (let i = 0; i < n; i++) { if (arr[i] === x){ ind = i; break; } } return ind; }

現在代碼的時間複雜度還為O(n)嗎？不確定，利用上一章的分析法就無法解決了。

不同情況

因為要查找的變量x 可能會出現在數組的任意位置。如果變量x恰好是數組中第一個元素，那麼函數就會break ，後續就不會繼續遍歷了，那時間複雜度就是O(1)。但如果恰好是數組中第末個元素，或者數組中不存在變量x 的話，那就需要把整個數組都遍歷一遍，時間複雜度就成了O(n)。所以，不同的情況下，這個函數的時間複雜度是不一樣的。

那为了表示代码在不同情况下的不同时间复杂度，需要了解以下三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度**。

理想情況

最好情況時間複雜度：在最理想的情況下，執行這段代碼的時間複雜度。比如說剛才那段函數，在最理想的情況下，要查找的變量x正好是數組的第一個元素，這種情況下對應的時間複雜度就是最好情況時間複雜度。

糟糕情況

最壞情況時間複雜度：在最糟糕的情況下，執行這段代碼的時間複雜度。比如說剛才那段函數，要查找的變量x正好是數組的第末個元素或者不在數組中存在，查找函數就會把數組都遍歷一遍，這種情況下對應的時間複雜度就是最壞情況時間複雜度。

平均情況

但是，最好情況時間複雜度和最壞情況時間複雜度對應的都是極端情況下的代碼複雜度，發生的概率其實並不大。

為了更好地表示平均情況下的複雜度，引入另一個概念：平均情況時間複雜度，簡稱為平均時間複雜度。

那如何分析平均時間複雜度呢，還是拿剛才那段查找函數來說：

要查找的變量x 在數組中的位置，有n+1 種情況：在數組的0～n-1 位置中和不在數組中。然後把每種情況下，查找需要遍歷的元素個數累加起來，然後再除以n+1，就可以得到需要遍歷的元素個數的平均值。

根據上章所說，時間複雜度的大O標記法中，可以省略掉係數、低階、常量，所以，把這個公式簡化之後，得到的平均時間複雜度就是O(n)。

但是上面計算的過程中，沒有考慮到概率的問題，因為出現在每個位置的概率是不一樣的，所以得重新計算，如下分析：

要查找的變量x，要么在數組裡，要么就不在數組裡。簡單標記這兩種情況下的概率都為1/2。另外，要查找的數據出現在0～n-1 這n 個位置的概率也是一樣的，為1/n。所以，根據概率乘法法則，要查找的數據出現在0～n-1 中任意位置的概率就是1/(2n)。那我們把每種情況發生的概率都考慮進去，計算表達式就變成了：

最後的結果也叫做概率中的加權平均值，那最後此段函數的平均時間複雜度就為O(n)。

這麼看，平均時間複雜度是不是好麻煩，還需要概率計算。實際上，在大多數情況下，我們並不需要區分最好、最壞、平均情況時間複雜度三種情況。很多時候，我們使用一個複雜度就可以滿足需求了。只有同一塊代碼在不同的情況下，時間複雜度有量級的差距，我們才會使用這三種複雜度表示法來區分。

均攤情況

接下來再看一個概念，特殊的平均時間複雜度：均攤時間複雜度。

先來看一個特殊的函數，分析下它的時間複雜度：

{ var arr = new Array(n); // n 代表任意数字var ind = 0; function add(num) { if (ind === arr.length) { var sum = 0; for (var i = 0; i < arr.length; i++) { sum += arr[i]; } arr[0] = sum; ind = 1; } arr[ind] = num; ind++; } }

add函數就是實現一個往數組中添加數據的功能。先定義一個任意長度的空數組，然後給數組添加數據。當達到數組長度後，也就是ind === array.length時，用for循環遍歷數組求和，將求和之後的sum值放到數組的第一個位置，然後再將新的數據插入。但如果數組一開始就有空的話，則直接將數據添加到數組中。

來分析下此函數的時間複雜度：

最理想的情況下，數組中有剩餘位置，我們只需要將數據添加到數組下標為ind的位置就可以了，所以最好情況時間複雜度為O(1)。最糟糕的情況下，數組中沒有剩餘位置，我們需要先做一次數組的遍歷求和，然後再添加數據，所以最壞情況時間複雜度為O(n)。

接下來分析需要計算的平均時間複雜度：

由於數組的長度是n，根據數據添加的位置的不同，可以分為n 種情況，每種情況的時間複雜度是O(1)。除此之外，還有一種特殊的情況，就是在數組沒有空閒空間時添加一個數據，這個時候的時間複雜度是O(n)。而且，這n+1 種情況發生的概率一樣，都是1/(n+1)。

所以根據大O表示法，平均時間複雜度就為O(1)。

其實add函數的平均複雜度不需要這麼複雜，接下來我們看看find函數和add函數的區別：

• find函數在極端情況下，時間複雜度才為O(1)。但add函數在大部分情況下，時間複雜度都為O(1)。只有個別情況下，時間複雜度才比較高，為O(n)。
• 對於add函數來說，O(1)時間複雜度的添加和O(n)時間複雜度的添加，出現的頻率是非常有規律的，而且有一定的前後順序，一般都是一個O(n)添加之後，緊跟著n-1 個O(1) 的添加操作，循環往復。

所以，針對這樣一種特殊場景的複雜度分析，我們並不需要像之前講平均複雜度分析方法那樣，找出所有的輸入情況及相應的發生概率，然後再計算加權平均值。

針對這種特殊的情況，我們引入了一種更加簡單的分析方法：攤還分析法。通過攤還分析得到的時間複雜度，叫均攤時間複雜度。

那如何使用攤還分析法來分析算法的均攤時間複雜度呢？

還是看add函數。每一次O(n) 的添加操作，都會跟著n-1 次O(1) 的添加操作，所以把耗時多的那次操作均攤到接下來的n-1 次耗時少的操作上，均攤下來，這一組連續的操作的均攤時間複雜度就是O(1)。這就是均攤分析的大致方法。

一般情況總結為：

對一個數據結構進行一組連續操作中，大部分情況下時間複雜度都很低，只有個別情況下時間複雜度比較高，而且這些操作之間存在前後連貫的時序關係，這個時候，我們就可以將這一組操作放在一塊兒分析，看是否能將較高時間複雜度那次操作的耗時，平攤到其他那些時間複雜度比較低的操作上。而且，在能夠應用均攤時間複雜度分析的場合，一般均攤時間複雜度就等於最好情況時間複雜度。

生活舉例

看高人如何把複雜度利用到生活中：

今天你準備去老王家拜訪下，可惜老王的愛人叫他去打個醬油，她告訴你說她限時n 分鐘給他去買。
那麼你想著以他家到樓下小賣部來回最多一分鐘，那麼“最好的情況”就是你只用等他一分鐘。
那麼也有可能遇到突發情況，比如說電梯沒電了，或者路上摔了一跤，天知道他去乾了什麼，用了n 分鐘。沒辦法，老婆有令，n 分鐘限時，那這就是“最壞的情況”。
那“平均時間複雜度” 就是他有可能是第1,2,3,...,n 中的某個分鐘回來，那平均就是1+2+3+...n/n，把所有可能出現的情況的時間複雜度相加除以情況數。
“均攤時間複雜度”的話就是把花時間多的分給花時間少的，得到一個中間值。假如n 是10 分鐘，那麼9 分鐘分4 分鐘到1 分鐘那，8 分3 給2...，那均攤下來就是5 分鐘。

總結

4 個概念

• 最好情況時間複雜度：代碼在最理想情況下執行的時間複雜度。
• 最壞情況時間複雜度：代碼在最糟糕情況下執行的時間複雜度。
• 平均情況時間複雜度：用代碼在所有情況下執行的次數的加權平均值表示。
• 均攤時間複雜度：在代碼執行的所有復雜度情況中絕大部分是最好情況時間複雜度，個別情況是最壞情況時間複雜度且發生具有時序關係時，可以將個別最壞情況時間複雜度均攤到最好情況時間複雜度上。基本上均攤結果就等於最好情況時間複雜度。

引入目的

• 同一段代碼在不同情況下時間複雜度會出現量級差異，為了更全面，更準確的描述代碼的時間複雜度，所以引入這4個概念。
• 代碼複雜度在不同情況下出現量級差別時才需要區別這四種複雜度。大多數情況下，是不需要區別分析它們的。

重點

如果有錯誤或者錯別字，還請給我留言指出，謝謝。

我們下期見。