1. 概述

时间复杂度是衡量算法执行效率的重要指标，表示算法运行时间随输入数据规模增长的变化趋势。在JavaScript开发中，理解时间复杂度有助于编写高性能代码，特别是在处理大规模数据时。

2. 大O表示法

大O表示法用于描述算法的最坏情况时间复杂度，重点关注增长趋势而非具体时间。

2.1 常见复杂度分类

2.2 复杂度比较

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2)

3. JavaScript中的时间复杂度分析

3.1 基本操作

// O(1) - 常数时间
const arr = [1, 2, 3];
arr[1]; // 数组访问
const obj = { a: 1 };
obj.a;  // 对象属性访问

3.2 循环结构

// O(n) - 线性时间
for (let i = 0; i < n; i++) {
  // 单层循环
}

// O(n^2) - 平方时间
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    // 嵌套循环
  }
}

// O(log n) - 对数时间
while (n > 1) {
  n = n / 2; // 每次问题规模减半
}

3.3 递归算法

// O(2) - 指数时间 (斐波那契数列朴素递归)
function fib(n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2);
}

// O(n) - 线性时间 (尾递归优化)
function fib(n, a = 0, b = 1) {
  if (n === 0) return a;
  return fib(n - 1, b, a + b);
}

4. JavaScript内置方法时间复杂度

4.1 数组方法

4.2 对象与集合

5. 优化策略

5.1 空间换时间

// 优化前: O(n^2)
function hasDuplicate(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 hasDuplicate(arr) {
  const seen = new Set();
  for (const item of arr) {
    if (seen.has(item)) return true;
    seen.add(item);
  }
  return false;
}

5.2 算法选择

• 排序: 使用内置sort()(O(n log n))而非手写冒泡排序(O(n^2))
• 搜索: 有序数组使用二分查找(O(log n))而非线性查找(O(n)))

5.3 避免常见陷阱

// 陷阱: 在循环中使用O(n)操作
for (let i = 0; i < arr.length; i++) {
  arr.unshift(i); // 每次unshift都是O(n)，整体变为O(n^2)
}

6. 实际案例分析

6.1 双重循环优化

// 优化前: O(n^2)
function findPair(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === target) return [i, j];
    }
  }
  return null;
}

// 优化后: O(n)
function findPair(arr, target) {
  const map = new Map();
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(arr[i], i);
  }
  return null;
}

6.2 递归优化

// 优化前: O(2)
function fib(n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2);
}

// 优化后: O(n) - 使用动态规划
function fib(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

7. 总结

理解时间复杂度是编写高效JavaScript代码的关键。通过：

1. 分析代码的执行流程
2. 了解内置方法的时间成本
3. 选择合适的算法和数据结构
4. 避免常见性能陷阱

可以显著提升应用程序性能，特别是在处理大规模数据时。