算法複雜度入門 - 讓新手也能了解 Big O
備註：本文內容由AI生成，僅供學習參考使用。
算法複雜度的重要性
在程式設計領域中，算法複雜度是評估程式效能的核心概念。對於初學者而言，Big O記法（Big O Notation）可能顯得抽象且難以理解。然而，掌握此概念對於解決LeetCode題目以及實際開發工作都具有重要意義。
本文將透過系統性的方式，結合實際例子和程式碼範例，幫助讀者建立對算法複雜度的清晰認知。
算法複雜度的基本概念
算法複雜度主要用於描述當輸入資料量增加時，算法執行時間或空間需求的增長趨勢。Big O記法提供了一種標準化的方式來表達這種增長關係。
O(1) - 常數時間複雜度
常數時間複雜度表示算法的執行時間與輸入資料量無關，無論資料量如何變化，執行時間都保持恆定。
實際例子： 從冰箱中取出特定飲料 無論冰箱內存放5瓶或50瓶飲料，取出單一瓶飲料的時間都是相同的。
// 陣列索引存取為O(1)複雜度
function getArrayElement(arr, index) {
return arr[index]; // 執行時間與陣列大小無關
}O(n) - 線性時間複雜度
線性時間複雜度表示算法的執行時間與輸入資料量成正比關係。
實際例子： 班級點名程序 若班級有10名學生，則需要進行10次點名；若有100名學生，則需要進行100次點名。執行時間與學生人數成正比。
// 線性搜尋為O(n)複雜度
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}O(n²) - 平方時間複雜度
平方時間複雜度表示算法的執行時間與輸入資料量的平方成正比，當資料量增加時，執行時間會急劇增長。
實際例子： 班級成員相互握手 假設班級有10名學生，每位學生需要與其他所有學生握手一次，總共需要進行45次握手。若學生人數增加到20人，則需要進行190次握手。人數增加一倍，握手次數增加四倍。
// 泡沫排序為O(n²)複雜度
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}O(log n) - 對數時間複雜度
對數時間複雜度表示算法的執行時間與輸入資料量的對數成正比，當資料量增加時，執行時間增長相對緩慢。
實際例子： 二分猜數字遊戲 假設需要猜測1到100之間的數字，每次猜測後會得到「太大」或「太小」的提示。採用二分搜尋策略：
- 第一次猜測50
- 若太大，下次猜測25
- 若太小，下次猜測75
此策略最多需要7次猜測即可找到答案（因為2⁷ = 128 > 100）。
// 二分搜尋為O(log n)複雜度
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}實際開發中的應用案例
案例一：用戶搜尋功能優化
在開發用戶搜尋功能時，初始實現可能採用簡單的線性搜尋：
// 初始實現 - O(n)複雜度
function searchUsers(users, keyword) {
return users.filter((user) => user.name.toLowerCase().includes(keyword.toLowerCase()));
}當用戶數量達到10萬時，每次搜尋操作可能需要數秒鐘的執行時間。透過引入索引結構和更高效的搜尋算法，可以顯著提升搜尋效能。
案例二：重複資料檢測優化
檢測陣列中是否存在重複元素的初始實現：
// 效能較差的實現 - O(n²)複雜度
function hasDuplicates(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) {
return true;
}
}
}
return false;
}優化後的實現：
// 優化實現 - O(n)複雜度
function hasDuplicates(arr) {
return new Set(arr).size !== arr.length;
}此優化將時間複雜度從O(n²)降低至O(n)，在處理大量資料時效能提升顯著。
常見複雜度比較表
| 複雜度 | 10筆資料 | 100筆資料 | 1000筆資料 | 實際應用 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 陣列索引存取 |
| O(log n) | 3 | 7 | 10 | 二分搜尋 |
| O(n) | 10 | 100 | 1000 | 線性搜尋 |
| O(n log n) | 33 | 664 | 9966 | 快速排序 |
| O(n²) | 100 | 10000 | 1000000 | 泡沫排序 |
從表格可以看出，當資料量增加時，O(n²)算法的執行次數呈現指數級增長，這在實際應用中是不可接受的。
空間複雜度考量
除了時間複雜度，空間複雜度也是算法分析的重要面向：
// 空間複雜度O(1) - 僅使用固定數量的變數
function calculateSum(arr) {
let total = 0;
for (let num of arr) {
total += num;
}
return total;
}
// 空間複雜度O(n) - 建立新的陣列
function duplicateArray(arr) {
return arr.map((x) => x * 2); // 建立與原陣列相同大小的新陣列
}在實際開發中，需要在時間複雜度和空間複雜度之間取得平衡，根據具體需求選擇合適的算法。
算法優化實務技巧
1. 避免巢狀迴圈結構
// 效能較差的實現 - O(n²)複雜度
function findCommonElements(arr1, arr2) {
const result = [];
for (let i = 0; i < arr1.length; i++) {
for (let j = 0; j < arr2.length; j++) {
if (arr1[i] === arr2[j]) {
result.push(arr1[i]);
}
}
}
return result;
}
// 優化實現 - O(n + m)複雜度
function findCommonElements(arr1, arr2) {
const set2 = new Set(arr2);
return arr1.filter(item => set2.has(item));
}2. 善用語言內建優化方法
// 自定義排序實現 - 可能為O(n²)複雜度
function customSort(arr) {
// 實現泡沫排序或插入排序
}
// 使用內建排序方法 - O(n log n)複雜度
arr.sort((a, b) => a - b);3. 提前終止策略
// 找到第一個符合條件的元素即終止搜尋
function findFirstMatch(arr, condition) {
for (let item of arr) {
if (condition(item)) {
return item; // 找到符合條件的元素即返回
}
}
return null;
}常見的效能陷阱
1. 字串拼接操作
// 看似簡單但實際為O(n²)複雜度
function concatenateStrings(arr) {
let result = '';
for (let str of arr) {
result += str; // 每次拼接都會重新建立字串
}
return result;
}
// 優化實現 - O(n)複雜度
function concatenateStrings(arr) {
return arr.join('');
}2. 迴圈中的重複計算
// 效能較差的實現
for (let i = 0; i < arr.length; i++) {
// 每次迴圈都重新計算length屬性
}
// 優化實現
const length = arr.length; // 預先計算
for (let i = 0; i < length; i++) {
// 迴圈邏輯
}複雜度分析的使用時機
小規模資料（< 1000筆）
在此規模下，不同複雜度算法之間的效能差異可能不明顯。此時程式碼的可讀性和維護性比效能優化更為重要。
大規模資料（> 10000筆）
當資料量較大時，複雜度差異會變得明顯。O(n²)算法可能導致用戶體驗嚴重下降，此時必須考慮算法優化。
即時系統應用
在遊戲或即時通訊等對延遲敏感的系統中，即使資料量不大，也需要仔細考慮每個操作的執行時間。
學習建議與總結
學習策略
- 概念優先於記憶：理解算法複雜度的原理比背誦公式更為重要
- 實例導向學習：透過實際問題分析來加深理解
- 工具輔助：善用瀏覽器開發者工具進行效能分析
- 漸進優化：先確保功能正確性，再進行效能優化
核心要點總結
算法複雜度分析的核心在於預測程式執行時間的增長趨勢：
- O(1)：執行時間與資料量無關
- O(log n)：資料量增加時，執行時間增長緩慢
- O(n)：執行時間與資料量成正比
- O(n²)：資料量增加一倍，執行時間增加四倍
在實際開發中，通常追求O(1)或O(log n)的查詢操作，O(n)的遍歷操作，以及O(n log n)的排序操作。避免使用O(n²)算法可以解決大部分效能問題。
掌握算法複雜度分析不僅有助於解決LeetCode題目，更能提升實際開發中的程式品質和用戶體驗。