點擊上方「五分鐘學算法」，選擇「星標」公眾號
重磅乾貨，第一時間送達
來源：面向大象編程
最近，有不少讀者留言或私信問我時間複雜度的分析方法。時間複雜度說難也不難，說簡單也不簡單，但它一定是我們學習算法的過程中過不去的一道坎。這篇文章就想給大家介紹一種快速分析時間複雜度的方法 —— 題型分類法。
網絡上關於時間複雜度分析的文章，大部分都充斥著教材裡的陳詞濫調：先講一大堆數學概念，什麼增長速度、漸進複雜度，看得讓人摸不著頭腦。我今天的文章不想跟你講這些虛的，只想跟你講講最實用的技巧，讓你迅速搞定面試中的時間複雜度分析。
我們在面試中需要分析時間複雜度，無非是以下兩種情況：
無論是哪種情況，你一定都清楚這道題的題型。那麼只要記住不同題型的時間複雜度分析方法，二叉樹套用二叉樹的分析法、動態規劃套用動態規劃的分析法，就能做到快速分析時間複雜度了。
下面是我總結出的不同題型的時間複雜度分析方法：
題型時間複雜度本文將介紹「數循環法」與「整體法」兩種方法、六類題型的全部分析技巧。針對這六類題型，文末有按不同題型分類的往期文章回顧，供大家參考！
一、數循環法數循環法，就是看代碼中有幾個循環、每個循環會執行幾次，來確定算法的時間複雜度。
我們必須要掌握的一個基礎知識是：在程序的三大基本結構（順序、分支、循環）中，只有循環能真正影響時間複雜度。一般情況下，我們可以直接忽略代碼中的順序結構、分支結構，直接看循環結構來判斷時間複雜度。
程序的三大基本結構數循環法典型題型：動態規劃類題目「數循環法」最典型的題型就是動態規劃了。我們以一道經典的「最長公共子序列（LCS）」問題來看看數循環法是怎麼發揮作用的。
（以下題解代碼來自文章：LeetCode 例題精講 | 15 最長公共子序列：二維動態規劃的解法，不了解 LCS 問題或不清楚解法的同學，可以參考這篇文章。）
最長公共子序列（LCS）的題解代碼如下：
public int longestCommonSubsequence(String s, String t) {
if (s.isEmpty() || t.isEmpty()) {
return 0;
}
int m = s.length();
int n = t.length();
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else {
if (s.charAt(i-1) == t.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
}
return dp[m][n];
}
根據數循環法的基本思路，我們可以直接忽略掉代碼中的各個細節，只看循環結構：
public int longestCommonSubsequence(String s, String t) {
...
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
...
}
}
...
}
數循環法要數兩個東西：循環的層數、每個循環執行的次數。在這個例子中，代碼有兩個循環，都是簡單的 for-i 循環：
那麼，算法的時間複雜度就是內外層循環次數之積，也就是
循環的不同層數：數組類題目很多數組類題目也可以用數循環法來分析時間複雜度。根據題目和解法的不同，循環可能有 1~3 層。數循環法對於不同層數的循環都是有效的。
例如，經典的「最大子數組和」題目（LeetCode 53. Maximum Subarray Sum），從暴力的三重循環到動態規劃的單層循環解法都有。
public int maxSubArray(int[] nums) {
int n = nums.length;
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int sum = 0;
for (int k = i; k <= j; k++) {
sum += nums[k];
}
res = Math.max(res, sum);
}
}
return res;
}
時間複雜度
public int maxSubArray(int[] nums) {
int n = nums.length;
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
res = Math.max(res, sum);
}
}
return res;
}
時間複雜度
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n+1];
dp[0] = 0;
int res = Integer.MIN_VALUE;
for (int k = 1; k <= n; k++) {
dp[k] = Math.max(dp[k-1], 0) + nums[k-1];
res = Math.max(res, dp[k]);
}
return res;
}
時間複雜度
不理解問題的動態規劃解法原理的同學，可以參考這篇文章：LeetCode 例題精講 | 16 最大子數組和：子數組類問題的動態規劃技巧
while 循環的處理方式：鍊表類題目在上面的例子中，代碼中的循環都是簡單的 for-i 循環。有些情況下，代碼中的循環是 while 循環，或是一些複雜的 for 循環。對於這種情況，我們就需要仔細分析循環的執行次數。
鍊表題型會經常用到 while 循環。我們用這道經典的「快慢指針」題目進行分析：LeetCode 876 - Middle of the Linked List。
（以下題解代碼來自文章：LeetCode 例題精講 | 05 雙指針×鍊表問題：快慢指針，對題目或解法不了解的同學可以參考。）
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
// fast 一次前進兩個元素，slow 一次前進一個元素
fast = fast.next.next;
slow = slow.next;
}
// 鍊表元素為奇數個時，slow 指向鍊表的中點
// 鍊表元素為偶數個時，slow 指向鍊表兩個中點的右邊一個
return slow;
}
可以看到，while 循環在 fast 指針到達鍊表尾部時結束。而 fast 指針初始位於鍊表的頭部，一次前進兩個元素。設鍊表的長度為
二、整體法 整體法一般涉及到遞歸和數據結構，不能直接用循環次數判定時間複雜度，而是要看代碼中處理了幾個元素，來確定算法的時間複雜度。
使用整體法進行分析的題型有：二叉樹、回溯法、DFS、BFS 等。下面我們分別舉例介紹。
二叉樹：看結點的個數《LeetCode 例題精講》系列中寫過好幾次二叉樹的解題技巧。這些二叉樹問題的解法都有一個共性：
實際上，大部分二叉樹問題都可以使用子問題方法與「三步走」套路來求解。我專門寫過一篇文章總結二叉樹問題的套路：二叉樹問題太複雜？「三步走」方法解決它！
二叉樹問題既然都是用遞歸求解，就沒有循環來讓我們使用「數循環法」。這時候，我們就需要使用整體法，通過遍歷結點的個數來判斷時間複雜度。
二叉樹問題的時間複雜度離不開一個變量
不過對於稍難一些的題目，也可能出現「重複遍歷」的情況。例如 LeetCode 437. Path Sum III 這道題：
給定一個二叉樹，它的每個結點都存放著一個整數值。找出路徑和等於給定數值的路徑總數。
路徑不需要從根結點開始，也不需要在葉結點結束，但是路徑方向必須是向下的（只能從父結點到子結點）。
由於題目中的路徑可能位於二叉樹的中部，不少人會寫出這樣的題解代碼：
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
return rootPathSum(root, sum)
+ pathSum(root.left, sum)
+ pathSum(root.right, sum);
}
int rootPathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int target = sum - root.val;
return (target == 0 ? 1 : 0)
+ rootPathSum(root.left, target)
+ rootPathSum(root.right, target);
}
這是一個典型的「雙遞歸」代碼，存在 pathSum 和 rootPathSum 兩個遞歸函數，它們會相互調用。這樣，一個結點會不止遍歷一次，算法的時間複雜度就不能簡單地用
也就是說，如果想在二叉樹問題中寫出
回溯法：看結果的個數回溯法類題目有一個非常簡單的時間複雜度分析指南：有多少個結果，時間複雜度就是多少。例如：
LeetCode 78. Subsets，求數組所有可能的子集。對於大小為