一、為什么需要復雜度分析？

想象你正在開發一個手機通訊錄應用，需要實現聯系人搜索功能。你有兩種算法可以選擇：

// 算法A：線性搜索
public Contact linearSearch(List<Contact> contacts, String name) {for (Contact c : contacts) {if (c.getName().equals(name)) {return c;}}return null;
}// 算法B：二分搜索（需要排序）
public Contact binarySearch(List<Contact> contacts, String name) {// 先排序（假設已實現）Collections.sort(contacts, Comparator.comparing(Contact::getName));int left = 0, right = contacts.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;int cmp = contacts.get(mid).getName().compareTo(name);if (cmp == 0) return contacts.get(mid);if (cmp < 0) left = mid + 1;else right = mid - 1;}return null;
}

問題：當聯系人數量很少時（如100人），兩種算法都很快。但當聯系人增長到10萬人時：

• 算法A可能需要10秒
• 算法B可能只需0.01秒

復雜度分析就是幫助我們預測算法在數據量增長時的表現，避免上線后才發現性能問題

二、時間復雜度：算法執行時間的增長趨勢

1. 基本概念

時間復雜度不是計算具體時間，而是描述算法執行時間隨數據規模增長的變化趨勢

2. 大O表示法

我們使用大O表示法描述時間復雜度，常見的有：

• O(1)：常數時間
• O(log n)：對數時間
• O(n)：線性時間
• O(n log n)：線性對數時間
• O(n2)：平方時間
• O(2?)：指數時間

// 示例1：數組隨機訪問
int getElement(int[] arr, int index) {return arr[index]; // 只需一次操作
}// 示例2：判斷奇偶
boolean isEven(int num) {return num % 2 == 0; // 一次計算
}

3. 常見時間復雜度詳解

(1) O(1)：常數時間

特點：執行時間不隨數據規模變化

// 示例1：數組隨機訪問
int getElement(int[] arr, int index) {return arr[index]; // 只需一次操作
}// 示例2：判斷奇偶
boolean isEven(int num) {return num % 2 == 0; // 一次計算
}

(2) O(log n)：對數時間

特點：數據量翻倍時，操作數只增加1

// 示例：二分查找
int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) return mid;if (arr[mid] < target) left = mid + 1;else right = mid - 1;}return -1;
}

操作次數：每次循環數據量減半，N個元素最多需要log?N次操作

(3) O(n)：線性時間

特點：執行時間與數據規模成正比

// 示例：遍歷數組
int findMax(int[] arr) {int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) max = arr[i];}return max;
}

// 示例：遍歷數組
int findMax(int[] arr) {int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) max = arr[i];}return max;
}

操作次數：N個元素需要N次比較

(4) O(n log n)：線性對數時間

特點：常見于高效排序算法

// 示例：歸并排序
void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = (left + right) / 2;mergeSort(arr, left, mid);     // T(n/2)mergeSort(arr, mid + 1, right); // T(n/2)merge(arr, left, mid, right);  // O(n)}
}
// 時間復雜度：T(n) = 2T(n/2) + O(n) = O(n log n)

(5) O(n2)：平方時間

特點：數據量翻倍時，時間增加4倍

// 示例1：冒泡排序
void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);}}}
}
// 操作次數：(n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ O(n2)// 示例2：矩陣乘法
int[][] multiply(int[][] A, int[][] B) {int n = A.length;int[][] C = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {for (int k = 0; k < n; k++) {C[i][j] += A[i][k] * B[k][j];}}}return C;
}
// 三重循環 → O(n3)

(6) O(2?)：指數時間

特點：數據量增加1，時間翻倍

// 示例：斐波那契遞歸
int fibonacci(int n) {if (n <= 1) return n;return fibonacci(n - 1) + fibonacci(n - 2);
}
// 時間復雜度：T(n) = T(n-1) + T(n-2) + O(1) ≈ O(2?)

4. 時間復雜度計算規則

1. 忽略常數：O(2n) → O(n)
2. 取最高階：O(n3 + n2 + n) → O(n3)
3. 忽略系數：O(3n2) → O(n2)
4. 對數底數忽略：O(log?n) → O(log n)

三、空間復雜度：算法占用內存的增長趨勢

1. 基本概念

空間復雜度描述算法運行過程中臨時占用存儲空間隨數據規模增長的變化趨勢

2. 常見空間復雜度

(1) O(1)：常數空間

特點：占用固定內存，不隨數據規模變化

// 示例：數組元素求和
int sum(int[] arr) {int total = 0;           // 1個變量for (int num : arr) {total += num;        // 無新空間}return total;
}

(2) O(n)：線性空間

特點：占用空間與數據規模成正比

// 示例1：數組復制
int[] copyArray(int[] arr) {int[] newArr = new int[arr.length]; // 長度為n的數組for (int i = 0; i < arr.length; i++) {newArr[i] = arr[i];}return newArr;
}// 示例2：遞歸深度
int factorial(int n) {if (n <= 1) return 1;return n * factorial(n - 1); // 遞歸深度n → O(n)棧空間
}

(3) O(n2)：平方空間

特點：常見于二維數據結構

// 示例：矩陣存儲
int[][] generateMatrix(int n) {int[][] matrix = new int[n][n]; // n×n的矩陣for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = i * j;}}return matrix;
}
// 占用空間：n2 → O(n2)

四、復雜度分析實戰

案例1：兩數之和

// 方法1：暴力枚舉
int[] twoSum(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[i] + nums[j] == target) {return new int[]{i, j};}}}return new int[0];
}
// 時間復雜度：O(n2)  空間復雜度：O(1)// 方法2：哈希表
int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[]{map.get(complement), i};}map.put(nums[i], i);}return new int[0];
}
// 時間復雜度：O(n)  空間復雜度：O(n)

案例2：歸并排序

void mergeSort(int[] arr) {if (arr.length <= 1) return;int mid = arr.length / 2;int[] left = Arrays.copyOfRange(arr, 0, mid); // O(n)int[] right = Arrays.copyOfRange(arr, mid, arr.length); // O(n)mergeSort(left);mergeSort(right);merge(arr, left, right);
}
// 時間復雜度：O(n log n)
// 空間復雜度：O(n)（遞歸棧O(log n) + 臨時數組O(n)）

五、復雜度優化策略

1. 時間優化技巧

• 空間換時間：使用哈希表減少查找時間
• 分治策略：歸并排序、快速排序
• 動態規劃：避免重復計算
• 雙指針：減少不必要的遍歷

2. 空間優化技巧

• 原地操作：冒泡排序、堆排序
• 迭代替代遞歸：減少棧空間
• 數據壓縮：位圖代替布爾數組

六、常見算法復雜度總結

算法名稱	時間復雜度	空間復雜度	應用場景
二分查找	O(log n)	O(1)	有序數據查找
快速排序	O(n log n)	O(log n)	通用排序
歸并排序	O(n log n)	O(n)	大數據排序
冒泡排序	O(n2)	O(1)	教學示例
深度優先搜索	O(V+E)	O(V)	圖遍歷
動態規劃	O(n2)	O(n)	最優解問題

七、實際開發中的復雜度分析

1. 數據庫查詢優化

-- O(n) 全表掃描
SELECT * FROM users WHERE name LIKE '%john%';-- O(log n) 索引查詢
SELECT * FROM users WHERE id = 10086;

2. 系統設計考慮

• 用戶量從1萬到1000萬時：
  • 時間復雜度O(n2)的算法會慢10000倍
  • 空間復雜度O(n)需要1000倍內存

3. 性能測試與復雜度驗證

// 測試不同規模數據下的執行時間
void testPerformance() {for (int n = 1000; n <= 1000000; n *= 10) {int[] arr = generateArray(n); // 生成n個元素的數組long start = System.nanoTime();algorithm(arr); // 運行算法long duration = System.nanoTime() - start;System.out.printf("n=%d, time=%.2f ms%n", n, duration / 1e6);}
}

八、復雜度分析的局限性

1. 忽略常數因子：O(100n)和O(n)視為相同
2. 不考慮硬件差異：SSD vs HDD
3. 不反映實際時間：只描述增長趨勢
4. 不適用于小數據量：小數據時簡單算法可能更快