大 O 表示法与时间复杂度分析

O(1)       常数级     哈希查找、数组按下标访问
O(log n)   对数级     二分查找、平衡树查找
O(n)       线性级     单层循环遍历
O(n log n) 线性对数   快排 / 归并 / 堆排序（排序的"天花板"）
O(n²)      平方级     双层循环（冒泡 / 选择 / 插入）
O(2ⁿ)      指数级     无剪枝回溯（n 一大会爆炸）
O(n!)      阶乘级     全排列枚举

// 运行环境：Node.js 14+
// 保存为 dsa-l1.js，执行：node dsa-l1.js

// O(1)：和 n 无关
function getFirst(arr) { return arr[0] }

// O(n)：循环正好执行 n 次
function sum(arr) {
  let s = 0
  for (let i = 0; i < arr.length; i++) s += arr[i]
  return s
}

// O(n²)：两层循环各 n 次
function bubbleBad(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]]
}

// O(log n)：规模每次减半
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1
  while (lo <= hi) {
    const mid = (lo + hi) >> 1          // 中间下标
    if (arr[mid] === target) return mid
    if (arr[mid] < target) lo = mid + 1 // 去右半边
    else hi = mid - 1                   // 去左半边
  }
  return -1
}

// O(n log n)：外层减半 × 内层线性（归并/快排主循环）
function mergeSort(arr) {
  if (arr.length <= 1) return arr
  const mid = arr.length >> 1
  const L = mergeSort(arr.slice(0, mid))   // 左半递归
  const R = mergeSort(arr.slice(mid))      // 右半递归
  return merge(L, R)                       // 合并两个有序数组 O(n)
}
function merge(L, R) {
  const out = []
  let i = 0, j = 0
  while (i < L.length && j < R.length) out.push(L[i] <= R[j] ? L[i++] : R[j++])
  return out.concat(L.slice(i), R.slice(j))
}

// 调用示例
console.log(sum([1, 2, 3, 4]))            // 10
console.log(binarySearch([1, 3, 5, 7], 5)) // 2
console.log(mergeSort([3, 1, 4, 2]))        // [1, 2, 3, 4]

① T(n) = T(n/2) + O(1)    → O(log n)   二分递归，如二分查找
② T(n) = 2T(n/2) + O(n)   → O(n log n) 分治，如归并/快排
③ T(n) = T(n-1) + O(1)    → O(n)       线性递归，如阶乘
④ T(n) = 2T(n-1) + O(1)   → O(2ⁿ)      斐波那契朴素递归，指数级！