算法基础：特性、复杂度与经典实现解析

平均比较次数 = 期望值 E[X]。 当 n 很大时，(n+1)/2 ≈ n/2。因为 n/2 与 (n+1)/2 的差异是常数 0.5，在大 O 表示法中忽略常数和低阶项，所以两者是等价的。

关系：最佳情况 ≤ 平均情况 ≤ 最坏情况。 在实际工程和理论分析中，最坏情况时间复杂度是最常用和最重要的标准。

渐进符号（时间复杂度表示法）

为了简化分析，我们忽略常数因子和低阶项，只关注随输入规模 n 增长的趋势。

三种主要的渐进符号

1. O（大 O 符号）- 渐进上界

   • 定义：T(n) = O(f(n))，表示存在正常数 C 和 n₀，使得对于所有 n ≥ n₀，有 T(n) ≤ C * f(n)。
   • 意义：表示算法运行时间的最坏情况增长趋势。
   • 例子：3n² + 2n + 1 是 O(n²)。

2. Ω（大Ω符号）- 渐进下界

   • 定义：T(n) = Ω(f(n))，表示存在正常数 C 和 n₀，使得对于所有 n ≥ n₀，有 T(n) ≥ C * f(n)。
   • 意义：表示算法运行时间的最佳情况增长趋势。

3. Θ（大Θ符号）- 渐进紧确界

   • 定义：T(n) = Θ(f(n))，当且仅当 T(n) = O(f(n)) 且 T(n) = Ω(f(n))。
   • 意义：表示算法运行时间的精确增长量级。

常见的时间复杂度等级（从优到劣）

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

当 n ≥ 4 时，n! > 2ⁿ 恒成立。

实际分析示例

对于算法 T(n) = an² + bn + c：

1. 我们忽略低阶项 bn 和常数项 c，因为当 n 很大时，n² 项占主导。
2. 我们忽略最高阶项 an² 的系数 a，因为不同计算机的常数因子不同，我们只关心增长趋势。
3. 最终，我们将其渐进时间复杂度表示为 O(n²)。

常见的时间复杂度与查找算法对应（JavaScript 示例）

1. 常数级 O(1) —— 哈希表（对象 / Map）查找

适用场景：通过键直接访问值，无需遍历。

const phoneBook = {
  "Alice": "123-4567",
  "Bob": "987-6543",
  "Charlie": "555-5555"
};

function findPhoneNumber(name) {
  return phoneBook[name]; // O(1)
}
console.log(findPhoneNumber("Alice")); // "123-4567"

⚠️ 注意：这是平均情况下的 O(1)，最坏情况（大量哈希冲突）可能退化为 O(n)，但现代 JS 引擎优化良好，通常视为 O(1)。

2. 对数级 O(log n) —— 二分查找（Binary Search）

前提：数组必须已排序。

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const 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; // 未找到
}

const sortedArr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sortedArr, 7)); // 输出 3

时间复杂度：每次循环将搜索范围减半 → O(log n)

3. 线性级 O(n) —— 顺序查找（Linear Search）

适用场景：无序数组、链表等无法利用结构特性的数据。

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // 找到，返回索引
    }
  }
  return -1; // 未找到
}

const unsortedArr = [10, 25, 3, 42, 17];
console.log(linearSearch(unsortedArr, 42)); // 输出 3

最坏情况需遍历全部 n 个元素 → O(n)

4. 平方级 O(n²) —— 暴力组合查找

严格来说，没有主流的'查找算法'是 O(n²)。但某些暴力匹配问题可能表现为 O(n²) 查找，例如查找数组中是否存在两个数之和等于目标值（暴力解法）。

function twoSumBruteForce(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]; // 返回索引对
      }
    }
  }
  return null;
}

const nums = [2, 7, 11, 15];
console.log(twoSumBruteForce(nums, 9)); // [0, 1]

这不是'单值查找'，而是组合查找，时间复杂度为 O(n²)。更优解可用哈希表实现 O(n)。

总结对照表：

3. 递归

阶乘函数（Factorial）是递归定义和递归实现的经典范例。

一、阶乘的递归数学定义

阶乘函数 $ n! $ 的递归定义如下：

$$ n! = \begin{cases} 1, & \text{if } n = 0 \quad \text{（边界条件 / base case）} \ n \times (n-1)!, & \text{if } n > 0 \quad \text{（递归体 / recursive case）} \end{cases} $$

✅ 注意：定义域：$ n \in \mathbb{N}_0 $（非负整数，包括 0）。$ 0! = 1 $ 是约定，也是组合数学的基础。

二、递归结构解析

三、JavaScript 递归实现

function factorial(n) {
  // 边界条件（递归终止条件）
  if (n === 0 || n === 1) {
    return 1;
  }
  // 递归体：用较小规模 (n-1)! 计算 n!
  return n * factorial(n - 1);
}

// 测试
console.log(factorial(0)); // 1
console.log(factorial(5)); // 120

💡 也可以只写 n === 0 作为边界，因为 1! = 1 × 0! = 1，但显式包含 n === 1 可略早终止。

四、执行过程示例（以 factorial(4) 为例）

factorial(4) └─ 4 * factorial(3) └─ 3 * factorial(2) └─ 2 * factorial(1) └─ 1 * factorial(0) └─ 1 ← 返回 → 1 * 1 = 1 → 2 * 1 = 2 → 3 * 2 = 6 → 4 * 6 = 24 

• 递归深度：n + 1 层（从 n 到 0）
• 调用栈：每次调用压入栈，返回时弹出

五、复杂度分析

✅ 时间复杂度：O(n)

• 共进行 n 次递归调用（从 n 到 1）
• 每次调用执行常数时间操作（乘法 + 函数调用）
• 总时间 ∝ n → T(n) = T(n−1) + O(1) ⇒ T(n) = O(n)

✅ 空间复杂度：O(n)

• 由于递归调用栈深度为 n，每层保存局部变量和返回地址
• 在 JavaScript 中，若 n 过大（如 > 10,000），会抛出 'Maximum call stack size exceeded' 错误

🔄 对比：迭代实现的空间复杂度为 O(1)

// 迭代版（更高效，无栈溢出风险）
function factorialIter(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

六、注意事项

大数问题：JavaScript 的 Number 类型在 n > 170 时会溢出（返回 Infinity），可改用 BigInt。

function factorialBig(n) {
  if (n === 0n) return 1n;
  return n * factorialBig(n - 1n);
}
console.log(factorialBig(100n)); // 支持超大整数

输入校验：实际应用中应检查 n 是否为非负整数。

if (n < 0 || !Number.isInteger(n)) throw new Error("n must be a non-negative integer");

七、递归展开法分析

分析递归算法时间复杂度的一种经典方法是建立递推关系式。

例 1：线性递归（阶乘）

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // 一次递归调用，规模减 1
}

递推式：

T(n) = T(n − 1) + O(1)

展开：

T(n) = T(n-1) + c = [T(n-2) + c] + c = T(n-2) + 2c = ... = T(1) + (n-1)c = O(n)

✅ 时间复杂度：O(n)

例 2：二分递归（二分查找）

function binarySearch(arr, low, high, target) {
  if (low > high) return -1;
  const mid = Math.floor((low + high) / 2);
  if (arr[mid] === target) return mid;
  if (target < arr[mid]) return binarySearch(arr, low, mid - 1, target);
  else return binarySearch(arr, mid + 1, high, target);
}

递推式：

T(n) = T(n/2) + O(1)

展开：

T(n) = T(n/2) + c = T(n/4) + 2c = ... = T(1) + c log n = O(log n)

✅ 时间复杂度：O(log n)

4. 分治法

分治法（Divide and Conquer）的核心思想是'分而治之'：把一个复杂的大问题，递归地分解为若干个规模更小、结构相同、相互独立的子问题，分别求解后再合并结果。

一、分治法的基本思想

✅ 适用条件

1. 可分解性：原问题能分解为若干个相同类型的子问题；
2. 子问题独立：子问题之间没有重叠（这是与动态规划的关键区别）；
3. 可合并性：子问题的解能高效合并为原问题的解；
4. 小问题可直接解：当问题规模足够小时（如 n=1），可直接求解。

二、分治法的三个标准步骤

三、经典案例：归并排序（Merge Sort）

归并排序是分治法的教科书级应用，完美体现上述三步。

📌 问题描述

对一个长度为 n 的数组进行升序排序。

✅ 分治三步解析

四、JavaScript 实现

// 合并两个已排序的数组
function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  // 双指针合并
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  // 添加剩余元素
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// 归并排序主函数
function mergeSort(arr) {
  // 基线条件（子问题足够小，直接返回）
  if (arr.length <= 1) {
    return arr;
  }
  // 1. 分解：分成两半
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  // 2. 求解：递归排序左右子数组
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);
  // 3. 合并：合并两个有序数组
  return merge(sortedLeft, sortedRight);
}

// 测试
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10])); // 输出：[3, 9, 10, 27, 38, 43, 82]

五、时间复杂度分析

使用递推式 + 主定理（Master Theorem）：

• 分解：O(1)
• 求解：2 个子问题，每个规模为 n/2 → 2T(n/2)
• 合并：遍历全部 n 个元素 → O(n)

递推式：T(n) = 2T(n/2) + O(n)

根据主定理：a = 2, b = 2, f(n) = n → log_b(a) = 1 → f(n) = Θ(n^log_b(a)) → 情况 2

✅ 所以时间复杂度为：O(n log n)

无论最好、最坏、平均情况，归并排序都是 O(n log n)，非常稳定！

空间复杂度：O(n)（用于临时合并数组 + 递归栈深度 O(log n)，但主要开销是合并时的辅助数组）

六、分治法 vs 动态规划 vs 贪心

✅ 记住：'独立子问题 → 分治；重叠子问题 → DP'

5. 动态规划

动态规划（Dynamic Programming, DP）的核心是重叠子问题和最优子结构，以及通过列表存储（记忆化）来避免重复计算的关键思想。

动态规划的设计步骤

1. 定义状态：用一个数组（一维、二维或更高维）dp[i] 或 dp[i][j] 来表示。参数定义了子问题的规模或范围。
2. 建立状态转移方程：描述了如何从一个或多个已知的、规模较小的子问题的解，推导出当前规模更大的子问题的解。
3. 确定初始条件和边界情况：明确最小的、不可再分的子问题的解，并正确地初始化状态数组。
4. 确定计算顺序并计算：确保在计算 dp[当前状态] 时，它所依赖的 dp[子状态] 都已经被计算并存储好了。
5. 构造最优解：有时我们不仅需要知道最优值，还需要知道如何得到它。

经典示例：斐波那契数列

问题：计算第 n 个斐波那契数 F(n)，其中 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)。

• 状态定义：dp[i] 表示 F(i) 的值。
• 状态转移方程：dp[i] = dp[i-1] + dp[i-2]。
• 初始条件：dp[0] = 0, dp[1] = 1。
• 计算顺序：自底向上，从 i=2 计算到 i=n。

动态规划解法（迭代法）

function fibDP(n) {
  if (n <= 1) return n;
  // 定义状态数组
  const dp = new Array(n + 1);
  // 初始条件
  dp[0] = 0; dp[1] = 1;
  // 状态转移
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

console.log(fibDP(10)); // 55
console.log(fibDP(50)); // 12586269025

空间优化版本

function fibOptimized(n) {
  if (n <= 1) return n;
  let prev1 = 1; // dp[i-1]
  let prev2 = 0; // dp[i-2]
  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

console.log(fibOptimized(10)); // 55

案例 2:0/1 背包问题

问题描述：有 n 个物品，每个物品有重量 w 和价值 v，背包容量为 W。每个物品只能选择 0 个或 1 个，求不超过背包容量的最大价值。

function knapsack01(weights, values, capacity) {
  const n = weights.length;
  // 第一步：定义状态
  // dp[i][w] 表示考虑前 i 个物品，背包容量为 w 时的最大价值
  const dp = new Array(n + 1);
  for (let i = 0; i <= n; i++) {
    dp[i] = new Array(capacity + 1).fill(0);
  }
  // 第三步：初始条件（dp[0][...]和 dp[...][0]已经初始化为 0）
  // 第四步：状态转移（自底向上计算）
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= capacity; w++) {
      // 第二步：状态转移方程
      // 情况 1：不选择第 i 个物品
      const skip = dp[i - 1][w];
      // 情况 2：选择第 i 个物品（前提是放得下）
      const currentWeight = weights[i - 1];
      const currentValue = values[i - 1];
      let take = 0;
      if (currentWeight <= w) {
        take = dp[i - 1][w - currentWeight] + currentValue;
      }
      // 取两种情况的最大值
      dp[i][w] = Math.max(skip, take);
    }
  }
  // 最大价值
  const maxValue = dp[n][capacity];
  // 第五步：构造最优解（找出具体选了哪些物品）
  const selectedItems = [];
  let w = capacity;
  for (let i = n; i > 0; i--) {
    if (dp[i][w] !== dp[i - 1][w]) {
      selectedItems.push(i - 1); // 记录物品索引
      w -= weights[i - 1]; // 减去该物品的重量
    }
  }
  return { maxValue, selectedItems: selectedItems.reverse() };
}

// 测试示例
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;
const result = knapsack01(weights, values, capacity);
console.log('最大价值:', result.maxValue); // 10
console.log('选择的物品索引:', result.selectedItems); // [0, 3]

为什么必须建整张表？

既然最终背包容量是 5，为什么还要算容量 0、1、2、3、4 的情况？直接算容量 5 不行吗？

答案是：不行！因为'容量 5 的最优解'依赖于'更小容量的最优解'。

想象你要知道'用前 2 个物品装满 5kg 背包最多值多少钱'，你就必须知道：'如果我拿第 2 个物品（比如书，3kg），那剩下的 5−3=2kg 空间，用前 1 个物品（苹果）最多能值多少钱？'

这就必须提前知道'容量 2'时的答案！如果你只算容量 5，你就不知道'剩下 2kg 能装多少价值'，也就无法判断'拿书是否划算'。

动态规划的每一步都站在前一步的肩膀上。容量 w 的解，依赖于所有小于 w 的解。所以，虽然你只关心容量 5，但容量 0~4 是通往答案的必经之路，缺一不可。

总结

通过这些 JavaScript 示例，我们可以看到动态规划的核心模式：

1. 定义状态：明确 dp 数组的含义
2. 状态转移方程：如何从已知状态推导新状态
3. 初始条件：最小的子问题解
4. 计算顺序：确保依赖的状态先被计算
5. 构造最优解：如果需要具体方案

动态规划将指数级的时间复杂度优化到多项式级别，是解决最优化问题的强大工具。