前言
數據結構和算法本身是為了解決“時間上的快”和“空間上的省”的問題，如何讓代碼運行得更快，如何讓代碼更省存儲空間，是一個非常重要的考量標準。
為什麼需要複雜度分析？而不是運行代碼，通過統計、監控就可以得到算法執行的時間和佔用的內存大小（稱之為事後統計法）？
首先，通過代碼運行統計確實是正確的，但是，測試結果依賴於測試環境，在不同的測試環境中得到的結果相差可能非常大。
其次，測試結果受數據規模的影響很大。如排序算法，極端情況下，如果數據已經是有序的，執行時間就會非常短。除此之外，如果測試數據規則太小，測試結果可能無法真實反應算法的性能。比如，對於小規模的數據排序，插入排序可能會比快速排序快。
大O複雜度表示法
那麼，如何根據代碼進行執行時間的估算呢？
首先，假設每行代碼的執行時間都是一樣的，然後進行統計。
如上圖所示的代碼中，總執行時間就是 1 + n + n = 1 + 2n 的執行時間。我們再來看一下下面這段代碼。
總執行時間就是 1 + n + n*n + n*n = 1+ n + 2n^2。
根據上文所示中，我們可以得到一個規則。代碼的執行時間T(n)與每行代碼的執行次數n成正比。
也就是說： T(n） = O（f（n））
T(n) 表示代碼執行時間
n表示數據規模大小
f(n)表示每行代碼執行的次數總和
O表示代碼執行時間T(n)與f(n)表達式成正比
所以，上圖中的1 + n + n*n + n*n = 1+ n + 2n^2 即 T(n) = O(1+n+2n^2)。
這就是時間複雜度表示法。大 O 時間複雜度實際上並不具體表示代碼真正的執行時間，而是表示代碼執 行時間隨數據規模增長的變化趨勢，所以，也叫作漸進時間複雜度（asymptotic time complexity），簡稱時間複雜度。
時間複雜度分析
前文中介紹了大O時間複雜度表示方法，那麼，如何分析一段代碼的時間複雜度呢？
#只關注循環次數最多的一段代碼
大O時間複雜度表示法只是表示一種變化趨勢，所以，通常情況下，會忽略公式中的常量、低階、係數，只需要記錄一個最大階的量級就可以了。所以，在分析一個算法、一段代碼的時間複雜度的時候，也只關注循環執行次數最多的那一段代碼就可以了。這段核心代碼執行次數n的量級，就是整段代碼要分析的時間複雜度。
再來看之前的一段代碼
在大O時間複雜度表示法中，該代碼的總執行時間就是 1 + n + n = 1 + 2n 的執行時間。1是常量級執行時間，與n的大小無關，所以對於複雜度並沒有影響。2n中的係數2也是可以忽略的。所有，該代碼的總時間複雜度就是O(n)。
#加法法則：總複雜度等於最級最大的那段代碼的複雜度
首先，第一段代碼中的時間複雜度就是O(n)，第二段代碼的時間複雜度是 n + 2n^2 = O(n^2)。
綜合這二段代碼的時間複雜度，取其中大的量級。所以，整段代碼的時間複雜度就是O(n^2)。
也就是說，總的時間複雜度就是等於量級最大的那段代碼的時間複雜度。
#乘法法則：嵌套代碼的複雜度等於嵌套內外代碼複雜度的乘積
如上圖所示，單獨看calc()方法，時間複雜度T1(n)=O(n)。但是由於nested()方法不是一個普通操作，nested()方法的時間複雜度T2(n)=O(n)。
所以，整體來看，calc()方法的總時間複雜度T(n) = T1(n) * T2(n) = O(n * n) = O(n^2)。
常見時間複雜度實例分析
複雜度中，O(2^n）與O(n!）中的n值越大，執行時間會急劇增加，效率非常低。正常需要進行避免。
#O(1)
常量級時間複雜度。一般情況下，只要算法中不存在循環語句、遞歸語句，即使有成千上萬行的代 碼，其時間複雜度也是Ο(1)。
#O(logn)、O(nlogn）
對數階時間複雜度非常常見，同時也是Y難分析的一種時間複雜度。我通過一個例子來說明一
下。
<code>i
=1
while
( i <= n) {
i
=i * 2;
}
/<code>
根據我們前面講的複雜度分析方法，第三行代碼是循環執行次數Y多的。所以，我們只要能計算
出這行代碼被執行了多少次，就能知道整段代碼的時間複雜度。
從代碼中可以看出，變量 i 的值從 1 開始取，每循環一次就乘以 2。當大於 n 時，循環結束。還 記得我們高中學過的等比數列嗎？實際上，變量 i 的取值就是一個等比數列。如果我把它一個一
個列出來，就應該是這個樣子的：
所以，我們只要知道 x 值是多少，就知道這行代碼執行的次數了。通過 2 =n 求解 x 這個問題我 們想高中應該就學過了，我就不多說了。x=log n，所以，這段代碼的時間複雜度就是 O(log n)。
現在，我把代碼稍微改下，你再看看，這段代碼的時間複雜度是多少
<code>i
=1
while
( i <= n) {
i
=i * 3;
}
/<code>
根據我剛剛講的思路，很簡單就能看出來，這段代碼的時間複雜度為 O(log n)。
實際上，不管是以 2 為底、以 3 為底，還是以 10 為底，我們可以把所有對數階的時間複雜度都 記為 O(logn)。為什麼呢？
我們知道，對數之間是可以互相轉換的，log n 就等於 log 2 * log n，所以 O(log n) = O(C * log n)，其中 C=log 2 是一個常量。基於我們前面的一個理論：在採用大 O 標記複雜度的時 候，可以忽略係數，即 O(Cf(n)) = O(f(n))。所以，O(log n) 就等於 O(log n)。因此，在對數階 時間複雜度的表示方法里，我們忽略對數的“底”，統一表示為 O(logn)。
如果你理解了我前面講的 O(logn)，那 O(nlogn) 就很容易理解了。還記得我們剛講的乘法法則 嗎？如果一段代碼的時間複雜度是 O(logn)，我們循環執行 n 遍，時間複雜度就是 O(nlogn) 了。而且，O(nlogn) 也是一種非常常見的算法時間複雜度。比如，歸併排序、快速排序的時間 複雜度都是 O(nlogn)。
#O(m+n)、O(m*n)-
我們再來講一種跟前面都不一樣的時間複雜度，代碼的複雜度由兩個數據的規模來決定。老規
矩，先看代碼！
從代碼中可以看出，m 和 n 是表示兩個數據規模。我們無法事先評估 m 和 n 誰的量級大，所以
我們在表示複雜度的時候，就不能簡單地利用加法法則，省略掉其中一個。所以，上面代碼的時 間複雜度就是 O(m+n)。
<code>int
cal(int m, int n) {
int
sum_1 = 0;
int
i = 1;
for
(; i < m; ++i) {
sum_1
=sum_1 + i;
int
sum_2 = 0;
int
j = 1;
for
(; j < n; ++j) {
sum_2
=sum_2 + j;
return
sum_1 + sum_2; }
/<code>
針對這種情況，原來的加法法則就不正確了，我們需要將加法規則改為：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法則繼續有效：T1(m)*T2(n) = O(f(m) * f(n))。
內容小結
複雜度也叫漸進複雜度，包括時間複雜度和空間複雜度，用來分析算法執行效率與數據規模之間
的增長關係，可以粗略地表示，越高階複雜度的算法，執行效率越低。常見的複雜度並不多，從 低階到高階有：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)
