1.3　復雜度分析

所有的數據結構教程都會把復雜度分析放在前面來講，這不僅是因為復雜度分析是基礎，更因為它們真的非常重要。學會了復雜度分析，才能夠對算法進行正確分析，從而寫出復雜度更優的算法。如果你對一種算法的復雜度推導很熟悉，就意味著你已經完全理解了這個算法。

算法的復雜度分析分為兩個方面：時間復雜度和空間復雜度，通常我們更加關注前者。兩者的分析方法類似，并且在大多數情況下，對空間復雜度的分析更為容易，本章將圍繞如何求時間復雜度展開。

通常來說，算法決定了程序的性能，性能可以從完成同一項任務所使用的時間的長短、占用內存的大小兩個方面去考量。內存大小可以清晰地用數字進行量化，但是運行時長，由于不同計算機的性能不同，執行時間也會不同，甚至有可能有數倍的差距，那么究竟應該如何衡量程序運行時間的長短呢？

《計算機程序設計藝術》的作者高德納（Donald Knuth）提出了一種方法，這種方法的核心思想很簡單，就是一個程序的運行時間主要和兩個因素有關：

1.執行每條語句的耗時。

2.執行每條語句的頻率。

前者取決于硬件，后者取決于算法本身和程序的輸入。在相同的硬件環境下，不同算法的執行時間只取決于語句的執行頻率，因此可以將對執行時間的關注進一步簡化為對執行頻率的關注。那么如何統計算法執行每條語句的頻率呢？我們舉個例子來說明。

如下是一段計算從1累加到n的代碼，使用了一層循環，并且借助了一個變量res來存儲計算結果。

上述代碼會執行n次循環體的內容，假設每一次執行時間都是常數，不妨假設其執行時間是x，res=0和return res的執行時間分別為y和z，那么總的執行時間就等于nx+y+z。如果粗略地將x、y和z都看成一樣的，那么可以得出總時間為(n +2)x，如下圖所示。

可以明顯看出，算法的運行時間和數據的規模成正比。

隨著數據規模的不斷擴大，即n的值成百上千倍地變大，從漸進的趨勢上講，我們常常忽略較小項，如上面的2x，而僅保留最大項，如上面的nx，這樣可以大大減少分析的工作量，因此這種復雜度分析方法也被稱為漸進復雜度分析。實際上，這在現實中也很常見，即程序運行時間往往取決于其中一小部分指令。

基于以上思想，產生了大O表示法，它是一種描述算法性能的記法，這種描述和編譯系統、機器結構、處理器的快慢等因素無關。假設參數n表示數據的規模，這里的O表示量級（order），比如說“二分查找的時間復雜度是O(logn)”，表示它需要“通過logn量級的操作去查找一個規模為n的數據結構”。這種估測對算法的理論分析和比較是非常有價值的，我們可以快速地對算法效率進行大致的估算。

例如，一個擁有較小系數的O(n2)算法在規模n較小的情況下可能比一個高系數的O(n)算法運行得更快，但是隨著n變得足夠大以后，具有較慢上升趨勢的算法必然運行得更快，因此在采用大O表示法表示復雜度時，可以忽略系數，這也是我們可以忽略不同性能的計算機執行時間差異的原因，因為你可以把不同性能的計算機性能差異看成系數的差異。

除此之外，我們還應該區分算法的最好情況、最壞情況和平均情況，更多關于復雜度分析的理論知識，讀者可以閱讀《算法》（第4版）中 1.4 節算法分析的內容獲得。

接下來，我們介紹幾種常見的復雜度以及其對應的分析方法。

1.3.1　迭代復雜度分析

下面介紹幾種常見的時間復雜度，絕大多數算法的時間復雜度都是如下中的一種。

●　第1類是常數階，即O(1)。

只要算法中不存在循環語句、遞歸語句，即使有成千上萬行的代碼，其時間復雜度也是O(1)。

●　第2類是多項式，例如O(n)、O(n2)、O(n3)。

判斷一個算法是不是屬于這種時間復雜度的一個簡單方法是關注循環執行次數最多的那一段代碼，這段代碼執行次數對應n的量級，就是整個算法的時間復雜度。如果是一層n的循環，那么時間復雜度就是O(n)；如果嵌套了兩層n的循環，那么時間復雜度就是O(n2)，以此類推。

上面的代碼進行了一層循環，那么時間復雜度就是O(n)。實際情況可能會比較復雜，需要結合具體的代碼邏輯進行判斷，代碼示例如下。

這是力扣（LeetCode）第739題每日溫度中使用單調棧解法的代碼。外層for循環和內層while循環嵌套，執行次數最多的代碼很顯然是while 循環內部的語句，那是不是說該算法的時間復雜度就是O(n2)呢？其實不是，該算法的時間復雜度為O(n)，其中n為數組長度。原因在于，內層while循環執行的總次數是n，究其根本是因為對于數組T中的每一項來說，其僅會進棧一次并出棧一次，因此內存代碼執行的總次數和數組長度線性相關。

●　第3類是對數階：O(logn)和O(nlogn)。

對數階同樣是一種非常常見的時間復雜度，多見于二分查找和一些排序算法。

二分查找的時間復雜度通常是O(logn)，一些基于比較的排序算法的時間復雜度可以達到O(nlogn)，典型的有快速排序、歸并排序。

上面的代碼是一個典型的二分查找，由于每次循環都可以將問題的規模縮減一半，其時間復雜度是O(logn)。

●　第4類是指數階O(2n)。

指數的增長非常恐怖，一個指數階的算法通常是不可用的，或者存在優化的空間。一個典型的例子是fibonacci數列的遞歸實現版本。

可以看出fibonacci(n)等價于fibonacci(n-1)+fibonacci(n-2)。這一過程可以持續下去，即fibonacci(n-1)等價于fibonacci(n-2)+fibonacci(n-3 )……如果你把上述每一個計算過程看成樹的一個節點，那么整個計算過程就像一棵很大的樹。一個節點分裂為2個節點，2個節點分裂為4個節點。

算法的時間復雜度和圖中樹的節點數同階，而樹的節點數的數量級為O(2n)，因此這個算法的時間復雜度是 O(2n)。可以看出其中有許多重復的計算，可以通過存儲記憶的方式進行優化。

●　第5類是階乘復雜度O(n!)。

旅行商問題（Travelling Salesman Problem，TSP）是著名的NP問題，暴力的解法可以枚舉點的排列，這種算法的時間復雜度是O(n!)。另外一個比較典型的問題是全排列。

如下代碼是力扣（LeetCode）第46題全排列的解法（這里使用了18.2節提供的回溯模板）。

我們來簡單分析一下上面代碼的執行過程，這樣可以幫助你理解O(n!)是如何計算出來的。

為了描述方便，假設最終生成的具體的排列是a，所有排列形成的全排列是A。上述計算全排列的過程，可以看成如下步驟。

●　先選擇a的第1個元素。

●　再選擇a的第2個元素。

●　……

●　直到a中的所有元素都被選擇，即a的長度和nums的長度相同。

上面的過程用圖來表示，則如下所示。

實際上，可以將其看作一個決策樹。樹的每一個非葉子節點都要進行選擇，選擇的范圍是其子節點。不考慮內部代碼，只考慮回溯過程，總的計算次數就是節點總數。不難得出如下結論。

●　第1層（不考慮開始的那一層）節點總數為n，其中n為nums數組的長度（下同）。

●　第2層節點總數為n×(n-1)。

●　……

●　第n層節點總數為n×(n-1)…×1。

因此節點總數應該是n+n×(n-1)+n×(n-1)×(n-2)+…+n×(n-1)…×1。忽略低次項，得到n×(n-1)…×1，很明顯這就是O(n!)，因此上面全排列的代碼時間復雜度大致是O(n!)。

1.3.2　遞歸算法復雜度分析

與迭代相比，遞歸在書寫上有很大的優勢，本書也大量使用了遞歸解法，因此掌握遞歸的時間復雜度分析也非常重要。接下來，我們來看一下如何分析遞歸算法的時間復雜度。

遞歸算法采用的是分治的思想，把一個大問題分解為若干個相似的子問題求解。識別子問題之間的遞歸公式是進行遞歸復雜度分析的前提和根本。這里介紹兩種方法來分析遞歸的時間復雜度，分別是遞歸樹法和代入法。

遞歸樹法

遞歸樹分析是一種將遞歸過程描述成樹結構的方法。初始樹只有一個節點，隨著每一次遞歸，樹的深度加1。每一層的節點數取決于具體的場景。

在得到遞歸樹后，將樹每層中的節點求和，然后將所有層的節點求和，就大致可以得出樹的總節點數n了。而整個算法的基本操作數等于樹上每一個節點的基本操作數t乘以樹的總節點個數n。

以歸并排序為例，它是一個典型的分治算法。其基本過程分成兩個階段：分與合。其中分的過程采用自頂向下的方式，每次將問題規模縮小一半，直到問題規模縮小到尋常情況，即可以被直觀解決的情況。合的過程恰好相反，采用自底向上的方式，將問題一步步解決，直到還原到原問題規模。

如果你將這兩個過程化成遞歸樹的話，就會發現這兩個過程遞歸樹的深度都是logn。而每一層的節點數都是n，也就是說總節點數是nlogn，而節點的基本操作數是常數（這一點讀者可以通過歸并代碼發現），因此總的算法時間復雜度為O(nlogn)。

代入法

這種分析方法需要一點數學知識，相對來說沒有那么直觀，這種方法的入手點在于遞歸公式。比如有如下遞歸公式：T(n)=T(n-1)+T(0)，如何求解其時間復雜度？

T(n)=T(n-1)+T(0)指的是規模為n的問題，可以轉化為規模為n-1的子問題和一個常數的操作。

我們來嘗試代入，就像高中數學那樣。

T(n)=T(n-1)+T(0)

=T(n-2)+T(0)+T(0)

=T(n-3)+T(0)+T(0)+T(0)

=T(0)+…+T(0)+T(0)+T(0)

=n×T(0)

可以得出其時間復雜度為O(n)。

趁熱打鐵，再來一個稍微復雜一點的：T(n)=2×T(n/2)+n，只要模仿上述過程進行代入操作即可。

T(n)=2×T(n/2)+n指的是規模為n的問題，可以轉化為規模為n/2的子問題和一個n的操作。

T(n)=2×T(n/2)+n

=4×T(n/4)+2×n/2+n

=…

=…4×n/4+2×n/2+n

也就是T(n)約等于logn個n相加，因此時間復雜度大致為O(nlogn)。當你熟練了上面的分析過程之后，下次看到這樣的遞推公式，甚至不需要分析，就會立馬想到對應的復雜度，這就是量變引起質變的過程。

除了上面提到的常見方法，進行復雜度分析的方法還有很多，比如數學歸納法，感興趣的讀者可以參考《算法設計與分析》和《算法導論》相關章節去學習、了解。

需要注意的是，遞歸算法的調用棧空間經常被大家忽略，其實我們可以將遞歸算法看作使用了棧的迭代算法，這個棧就是遞歸中的調用棧，因此計算遞歸的空間復雜度需要加上開辟的棧空間。一個遞歸算法的調用棧大小取決于遞歸的最大深度。如果你能畫出遞歸樹的話，這其實就是遞歸樹的最大深度。

最后給大家列舉幾種常見的時間復雜度的趨勢對比圖，手繪圖并不精確，但也能直觀地反映出不同時間復雜度的趨勢變化。我們也會在20.1節看限制條件部分進一步介紹關于復雜度的實用技巧。