大多數專案變慢，不是因為語言不夠快，而是我們的做法繞太遠。

演算法講的不是炫技，而是取捨：時間 vs 空間、一次就做完 vs 拆小分工。這篇用工程視角帶你梳理：什麼是演算法、為什麼在產品規模放大後變得關鍵，它在前端事件迴圈與後端 I/O 裡各扮演什麼角色。

接著用可複製的 JavaScript 範例走過排序、二分搜尋、BFS/DFS、Dijkstra、動態規劃與回溯，示範如何量測、何時換策略（例如小資料選簡單、資料暴增改分治或快取）。你會看到清楚的決策框架，而不是空談複雜度：當資料帶著雜訊、需求一直改、部屬資源有限時，怎麼用最少的力氣把體感速度拉回來。希望本篇文章能夠幫助到需要的您。

// 合併排序：穩定排序，時間 O(n log n)，空間 O(n)
function mergeSort(arr, cmp = (a, b) => a - b) {
  if (arr.length <= 1) return arr.slice(); // 回傳拷貝避免就地修改
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid), cmp);
  const right = mergeSort(arr.slice(mid), cmp);
  return merge(left, right, cmp);
}

function merge(a, b, cmp) {
  const res = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (cmp(a[i], b[j]) <= 0) {
      res.push(a[i++]); // <= 保持穩定性
    } else {
      res.push(b[j++]);
    }
  }
  while (i < a.length) res.push(a[i++]);
  while (j < b.length) res.push(b[j++]);
  return res;
}

// 使用
const nums = [5, 1, 4, 2, 8, 5];
console.log(mergeSort(nums)); // [1, 2, 4, 5, 5, 8]

重點：穩定排序可保留相同鍵的原本相對順序，對多鍵排序（次要鍵/主要鍵）很有用。

2. 快速排序（Quick Sort）— 平均 O(n log n)，就地、快

// 快速排序（原地）：平均 O(n log n)，最壞 O(n^2)
function quickSort(arr, cmp = (a, b) => a - b, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;
  const pivotIndex = partition(arr, cmp, left, right);
  quickSort(arr, cmp, left, pivotIndex - 1);
  quickSort(arr, cmp, pivotIndex + 1, right);
  return arr;
}

function partition(arr, cmp, left, right) {
  // 以中點作為樞紐，可降低最壞情況機率；也可改用隨機樞紐
  const mid = left + ((right - left) >> 1);
  const pivot = arr[mid];
  [arr[mid], arr[right]] = [arr[right], arr[mid]];
  let i = left;
  for (let j = left; j < right; j++) {
    if (cmp(arr[j], pivot) <= 0) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

// 使用
const data = [9, 3, 7, 1, 2, 8];
console.log(quickSort(data)); // 原地排序

小訣竅：實務上常用「三數取中」或隨機樞紐降低退化機率；亦可在小陣列改用插入排序混合提升表現。

3. 二分搜尋（Binary Search）— O(log n）

// 在已排序陣列中搜尋 target，回傳索引，否則回傳 -1
function binarySearch(sortedArr, target, cmp = (a, b) => a - b) {
  let lo = 0, hi = sortedArr.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    const c = cmp(sortedArr[mid], target);
    if (c === 0) return mid;
    if (c < 0) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// 變體：lower_bound（第一個 >= target 的位置）
function lowerBound(sortedArr, target, cmp = (a, b) => a - b) {
  let lo = 0, hi = sortedArr.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (cmp(sortedArr[mid], target) < 0) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// 使用
const sorted = [1, 3, 3, 5, 8, 13];
console.log(binarySearch(sorted, 5));    // 3
console.log(lowerBound(sorted, 3));      // 1（第一個 3 的位置）

4. BFS / DFS（圖與樹的遍歷）

// 無向圖：鄰接表表示
class Graph {
  constructor(n) {
    this.n = n;
    this.adj = Array.from({ length: n }, () => []);
  }
  addEdge(u, v) {
    this.adj[u].push(v);
    this.adj[v].push(u);
  }
}

function bfs(graph, start) {
  const dist = Array(graph.n).fill(Infinity);
  const q = [];
  dist[start] = 0;
  q.push(start);
  let head = 0; // O(1) 佇列索引，避免 shift O(n)
  while (head < q.length) {
    const u = q[head++];
    for (const v of graph.adj[u]) {
      if (dist[v] === Infinity) {
        dist[v] = dist[u] + 1;
        q.push(v);
      }
    }
  }
  return dist;
}

function dfs(graph, start) {
  const visited = Array(graph.n).fill(false);
  const order = [];
  (function go(u) {
    visited[u] = true;
    order.push(u);
    for (const v of graph.adj[u]) {
      if (!visited[v]) go(v);
    }
  })(start);
  return order;
}

// 使用
const g = new Graph(6);
g.addEdge(0,1); g.addEdge(0,2); g.addEdge(1,3); g.addEdge(2,4); g.addEdge(4,5);
console.log(bfs(g, 0)); // [0,1,1,2,2,3]
console.log(dfs(g, 0)); // 例如 [0,1,3,2,4,5]

提示：在前端長圖遍歷可能卡住主執行緒，可將遍歷分片執行，或把工作丟到 Web Worker。

5. Dijkstra（非負權最短路徑）

// 使用二元小頂堆作優先佇列
class MinHeap {
  constructor() { this.a = []; }
  size() { return this.a.length; }
  push(x) { this.a.push(x); this._up(this.a.length - 1); }
  pop() {
    if (!this.a.length) return null;
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length) { this.a[0] = last; this._down(0); }
    return top;
  }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.a[p][0] <= this.a[i][0]) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  _down(i) {
    const n = this.a.length;
    while (true) {
      let m = i, l = i*2+1, r = i*2+2;
      if (l < n && this.a[l][0] < this.a[m][0]) m = l;
      if (r < n && this.a[r][0] < this.a[m][0]) m = r;
      if (m === i) break;
      [this.a[m], this.a[i]] = [this.a[i], this.a[m]];
      i = m;
    }
  }
}

function dijkstra(adj, src) {
  const n = adj.length;
  const dist = Array(n).fill(Infinity);
  const heap = new MinHeap();
  dist[src] = 0;
  heap.push([0, src]); // [距離, 節點]

  while (heap.size()) {
    const [d, u] = heap.pop();
    if (d !== dist[u]) continue; // 舊條目
    for (const [v, w] of adj[u]) {
      if (dist[v] > d + w) {
        dist[v] = d + w;
        heap.push([dist[v], v]);
      }
    }
  }
  return dist;
}

// 使用（有向或無向皆可；此例以有向為例）
const adj = [
  [[1,2],[2,5]],  // 0->1(2), 0->2(5)
  [[2,1],[3,3]],  // 1->2(1), 1->3(3)
  [[3,1]],        // 2->3(1)
  []              // 3
];
console.log(dijkstra(adj, 0)); // [0,2,3,4]

6. 動態規劃：最長遞增子序列（LIS）O(n log n）

// 回傳 LIS 長度；若要重建路徑可另外儲存前驅
function lengthOfLIS(nums) {
  const tails = []; // tails[k] = 長度為 k+1 的遞增序列之最小可能尾值
  for (const x of nums) {
    let i = 0, j = tails.length;
    while (i < j) { // 二分找第一個 >= x 的位置
      const m = (i + j) >> 1;
      if (tails[m] < x) i = m + 1; else j = m;
    }
    tails[i] = x;
  }
  return tails.length;
}

console.log(lengthOfLIS([10,9,2,5,3,7,101,18])); // 4 (2,3,7,101)

7. 回溯：子集合（含重複元素去重）

function subsetsWithDup(nums) {
  nums.sort((a,b)=>a-b);
  const res = [];
  const path = [];
  function backtrack(start) {
    res.push(path.slice());
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i-1]) continue; // 去重
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }
  backtrack(0);
  return res;
}

console.log(subsetsWithDup([1,2,2]));
// [[],[1],[1,2],[1,2,2],[2],[2,2]]

8. 字串匹配：KMP（線性時間）

// 回傳所有匹配起點
function kmpSearch(text, pattern) {
  if (pattern.length === 0) return [0];
  const lps = buildLPS(pattern);
  const res = [];
  let i = 0, j = 0;
  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++; j++;
      if (j === pattern.length) {
        res.push(i - j);
        j = lps[j - 1];
      }
    } else {
      if (j > 0) j = lps[j - 1];
      else i++;
    }
  }
  return res;
}

function buildLPS(p) {
  const lps = Array(p.length).fill(0);
  let len = 0, i = 1;
  while (i < p.length) {
    if (p[i] === p[len]) {
      lps[i++] = ++len;
    } else if (len > 0) {
      len = lps[len - 1];
    } else {
      lps[i++] = 0;
    }
  }
  return lps;
}

console.log(kmpSearch("ababcabcabababd", "ababd")); // [10]

9. 貪心：活動選擇（最多不重疊區間）

// 輸入：[ [start, end], ... ]，選擇最多不重疊活動
function selectMaxActivities(intervals) {
  // 依結束時間排序
  intervals.sort((a, b) => a[1] - b[1]);
  const res = [];
  let lastEnd = -Infinity;
  for (const [s, e] of intervals) {
    if (s >= lastEnd) {
      res.push([s, e]);
      lastEnd = e;
    }
  }
  return res;
}

console.log(selectMaxActivities([[1,3],[2,4],[3,5],[0,6],[5,7],[8,9]]));
// 可能結果：[[1,3],[3,5],[5,7],[8,9]]

效能量測與實務優化

1. 量測

function bench(fn, input, times = 10) {
  const { performance } = globalThis;
  const runs = [];
  for (let i = 0; i < times; i++) {
    const cloned = typeof structuredClone === "function"
      ? structuredClone(input)
      : JSON.parse(JSON.stringify(input)); // 粗略拷貝（注意循環參照）
    const t0 = performance.now();
    fn(cloned);
    const t1 = performance.now();
    runs.push(t1 - t0);
  }
  runs.sort((a,b)=>a-b);
  const median = runs[Math.floor(runs.length / 2)] || 0;
  return { medianMs: median, runsMs: runs };
}

注意：量測時盡量固定輸入大小與分布，並多跑幾次取中位數，避免 JIT 暖機與雜訊影響。

2. 前端避免阻塞

分片運算：把大計算切小塊，用 requestIdleCallback、setTimeout(0) 或微任務調度。

Web Worker：把 CPU 密集工作移出主執行緒。

資料結構選擇：例如大量 push/pop 從尾端的情況下，Array 很適合；若需頻繁從頭端移除，請用索引佇列技巧或自製佇列。

3. 後端（Node.js）

避免在熱路徑中同步阻塞（如同步檔案 IO）。

CPU 密集任務可用 worker_threads 或外部服務分擔。

善用串流處理（不一次把大檔載入記憶體）。

設計與選擇演算法的實用心法

1. 先清楚定義輸入/輸出與限制（上限 n、是否需要穩定、是否可近似）。

2. 先挑簡單可靠的（可行、好維護）→ 再視需求優化。

3. 證明或直覺 + 實測並行：先估 Big-O，再用 benchmark 驗證。

4. 留意最壞情況（快速排序退化、Hash 碰撞、惡意輸入）。

5. 把常見問題類型化：

順序相關 → 排序/貪心/DP

路徑/連通 → 圖演算法

子結構重複 → DP

解空間爆炸 → 回溯 + 剪枝/啟發式

6. 工程化：測試、型別（TS）、Lint、文件、可觀測性（log/metrics）。

常見陷阱與邊界案例

1. 空輸入 / 單元素：排序、搜尋、平均值都要處理。

2. 重複值：穩定性需求？二分搜尋找「第一個 ≥ x」或「最後一個 ≤ x」。

3. 整數溢位/精度：JS number 精度有限，需用 BigInt 或字串演算法。

4. 遞迴深度：資料太深可能 stack overflow；改寫為迭代或手動堆疊。

5. 不可變資料結構：在 React/狀態管理中常見，避免直接突變造成難以追蹤的狀態錯誤。

6. 資料預處理：排序一次 + 多次查詢 → 整體更省。

把演算法帶進產品場景（思考框架）

電商排序：多鍵排序（價格、評分、上架時間），可先依主要鍵排序，再用「穩定排序」串接次要鍵。

路線規劃：Dijkstra/A*；路網很大就做分區與快取。

推薦/搜尋：倒排索引 + 排序；字串匹配與相似度量測。

風控/偵測：圖關係 + BFS/社群偵測（進階）。

儀表板：大量資料彙整，先分桶/近似聚合，避免每次全掃。

總結

演算法不是競賽專屬，它是日常工程的效率語言。先把問題說清楚、找出限制，再挑一個對的思路與能維護的實作。掌握基本盤（排序、搜尋、圖、DP、回溯），你就能在 JavaScript 或任何語言裡，把「做得出來」提升到「做得好」。

演算法與資料結構(js) : 什麼是演算法 ? 相關觀念、種類、實作與範例

目錄

什麼是「演算法」？

為什麼需要演算法？

演算法在程式設計中扮演什麼角色？

可以把軟體系統想成三層：

演算法決定：

演算法的複雜度：時間與空間

分析演算法常用 Big-O 記號：

常見直覺：

演算法的主要種類與典型思路

1. 排序（Sorting）

2. 搜尋（Searching）

3. 分治（Divide and Conquer）

4. 貪心（Greedy）

5. 動態規劃（Dynamic Programming, DP）

6. 回溯（Backtracking）與搜尋

7. 圖演算法（Graph）

8. 字串演算法

9. 隨機化與近似

在 JavaScript 中如何使用演算法？

1. JS 的特性與注意點

2. 實作建議流程

JavaScript 演算法範例

1. 合併排序（Merge Sort）— 穩定、O(n log n)