时间复杂度

1. 什么是时间复杂度？

时间复杂度（Time Complexity）描述的是 算法的运行时间如何随着输入数据规模（n）的增长而变化。 即时间或空间随数据规模增长的变化趋势。
时间复杂度通常用 大 O 表示法（Big-O Notation） 表示，如 O(1)、O(n)、O(log n) 等。
它们是计算机科学中非常重要的概念，尤其在面试和优化代码时经常被问到。

2. 常见时间复杂度对比

3. 详细解释

（1）O(1) — 常数时间

• 特点：操作时间与数据规模 n 无关，无论 n 多大，耗时固定。
• 例子：
  • 数组按索引访问：arr[5] 直接跳转到内存地址，无需遍历。
  • 哈希表（HashMap）查找：通过哈希函数计算位置，理想情况下一次找到。
• 代码示例：

  int[] arr = {1, 2, 3};
  int x = arr[1]; // O(1)，直接访问索引 1
  

（2）O(log n) — 对数时间

• 特点：操作时间随 n 增长呈对数增长（增长速度远慢于线性）。
• 核心思想：每一步将问题规模减半（如二分查找）。
• 例子：
  • 二分查找：在有序数组中查找元素，每次排除一半数据。
  • 平衡二叉搜索树（如 TreeMap）：每次比较缩小搜索范围。
• 代码示例：

  // 二分查找（O(log n)）
  int binarySearch(int[] arr, int target) {
      int left = 0, right = arr.length - 1;
      while (left <= right) {
          int mid = left + (right - left) / 2;
          if (arr[mid] == target) return mid;
          else if (arr[mid] < target) left = mid + 1;
          else right = mid - 1;
      }
      return -1;
  }
  

（3）O(n) — 线性时间

• 特点：操作时间与数据规模 n 成正比。
• 例子：
  • 遍历数组/链表：需要逐个访问每个元素。
  • 线性搜索：在无序列表中查找特定值。
• 代码示例：

  // 遍历数组（O(n)）
  for (int num : arr) {
      System.out.println(num);
  }
  

（4）O(n log n) — 线性对数时间

• 特点：常见于高效排序算法，比 O(n²) 快，但比 O(n) 慢。
• 例子：
  • 快速排序、归并排序：通过分治策略减少比较次数。
• 代码示例：

  Arrays.sort(arr); // Java 默认使用快速排序（O(n log n)）
  

（5）O(n²) — 平方时间

• 特点：操作时间与 n² 成正比，性能较差。
• 例子：
  • 冒泡排序、选择排序：嵌套循环遍历所有元素对。
  • 嵌套循环：如遍历二维数组。
• 代码示例：

  // 冒泡排序（O(n²)）
  for (int i = 0; i < arr.length; i++) {
      for (int j = i + 1; j < arr.length; j++) {
          if (arr[i] > arr[j]) swap(arr, i, j);
      }
  }
  

4. 如何直观理解？

假设 n = 1000（数据量）：

5. 为什么重要？

• 优化代码：选择更低时间复杂度的算法可以大幅提升性能（尤其是大数据量时）。
• 面试必考：大厂面试常要求分析代码的时间复杂度。
• 系统设计：高并发场景下，O(n²) 的算法可能导致服务崩溃。

6. 常见误区

1. 忽略常数项：
   O(2n) 和 O(100n) 都记作 O(n)，因为大 O 表示法关注的是增长趋势。
2. 混淆最好/最坏情况：
   比如快速排序的最坏时间复杂度是 O(n²)（当数组已排序时），但平均是 O(n log n)。
3. 忽视空间复杂度：
   有些算法（如归并排序）时间高效但需要额外空间（O(n)）。

空间复杂度

空间复杂度（Space Complexity） 是衡量算法在运行过程中临时占用存储空间大小的量度，表示算法所需的额外内存空间随输入数据规模（n）增长的变化趋势。和时间复杂度一样，空间复杂度也用大 O 表示法（Big-O Notation）描述。

1. 空间复杂度的核心概念

• 额外空间：指除了输入数据本身占用的空间外，算法运行所需的临时存储空间（如变量、栈空间、递归调用等）。
• 原地算法（In-place）：空间复杂度为 O(1) 的算法，即不需要额外空间（如冒泡排序、堆排序）。
• 非原地算法：需要额外空间的算法（如归并排序 O(n)）。

2. 常见空间复杂度对比

3. 具体示例分析

(1) O(1) — 常数空间

算法运行期间，额外空间固定，与输入规模 n 无关。

// 示例：交换两个变量的值（无需额外数组）
void swap(int a, int b) {
    int temp = a; // 仅用 1 个临时变量
    a = b;
    b = temp;
}

典型算法：

• 冒泡排序、选择排序、插入排序（原地排序）。

(2) O(n) — 线性空间

额外空间与输入规模 n 成正比。

// 示例：将数组复制到新数组
int[] copyArray(int[] arr) {
    int[] newArr = new int[arr.length]; // 额外空间 O(n)
    for (int i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

典型算法：

• 归并排序（需临时数组）、哈希表（存储键值对）、递归调用栈（最坏情况）。

(3) O(log n) — 对数空间

常见于递归算法，每次递归调用减少问题规模。

// 示例：二分查找的递归实现
int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) {
        return binarySearch(arr, target, mid + 1, right); // 递归调用
    } else {
        return binarySearch(arr, target, left, mid - 1);
    }
}

典型算法：

• 快速排序的递归调用栈（平均 O(log n)，最坏 O(n)）、平衡二叉树的递归操作。

(4) O(n²) — 平方空间

常见于需要二维数组的算法。

// 示例：动态规划中的二维表格
int[][] dp = new int[n][n]; // 空间 O(n²)

典型场景：

• 动态规划问题（如最长公共子序列）、邻接矩阵存储图。

4. 空间复杂度 vs 时间复杂度

5. 实际应用中的权衡

• 内存敏感场景（如嵌入式设备）：优先选择空间复杂度低的算法（如原地排序）。
• 时间敏感场景（如实时系统）：可能牺牲空间换取时间（如用哈希表加速查找）。

6. 常见误区

1. 混淆“输入空间”和“额外空间”：
   空间复杂度通常只计算算法运行时额外申请的空间，输入数据本身不纳入计算。

   // 以下算法的空间复杂度是 O(1)，而非 O(n)
   void printArray(int[] arr) { // arr 是输入，不计算
       for (int num : arr) {
           System.out.println(num);
       }
   }
   

2. 忽略递归调用的栈空间：
   递归算法的空间复杂度取决于递归深度（如斐波那契数列递归版为 O(n)）。

总结

• 空间复杂度 关注算法对内存的额外消耗。
• 常见级别：O(1) < O(log n) < O(n) < O(n²)。
• 优化策略：根据场景选择时间或空间更优的算法，例如：
  • 内存有限时用堆排序（O(1) 空间），而非归并排序（O(n) 空间）。
  • 递归算法可改为迭代版本以减少栈空间（如用循环实现斐波那契数列）。

理解对数 log

在时间复杂度 O(log n) 中，log 指的是 对数（logarithm），通常默认以 2 为底（即 log₂ n），表示的是“将问题规模 n 不断除以 2，直到结果为 1 所需的次数”。这种对数增长的特点是：数据量 n 大幅增加时，操作次数增长非常缓慢。

1. 为什么是 log₂ n？

• 二分思想：O(log n) 常见于分治算法（如二分查找、平衡二叉树操作），每一步都将问题规模 减半，因此底数默认为 2。
  • 例如：二分查找每次排除一半数据，直到找到目标。
• 数学定义：
  log₂ n = x 等价于 2ˣ = n。
  即“2 的 x 次方等于 n”。

2. 为什么 n=1000 时操作次数约为 10？

计算 log₂ 1000：

1. 手动估算：
   • 2¹⁰ = 1024 ≈ 1000，因此 log₂ 1000 ≈ 10。
2. 精确计算：
   • log₂ 1000 ≈ 9.96578，向上取整为 10 次操作。

直观理解：
在二分查找中，若数组长度为 1000，最坏情况下需要 约 10 次比较 才能确定元素是否存在：

第1次：1000 → 剩余 500  
第2次：500  → 剩余 250  
第3次：250  → 剩余 125  
...  
第10次：1    → 找到或确认不存在

3. 不同底数的 log 会影响时间复杂度吗？

• 大 O 表示法忽略常数：无论底数是 2、10 还是自然对数 e，O(log₂ n)、O(log₁₀ n) 和 O(ln n) 都记作 O(log n)，因为对数之间可以通过换底公式转换（相差一个常数系数）。
  换底公式：
  logₐ b = logₐ c × log_c b
  例如：log₁₀ n = log₁₀ 2 × log₂ n ≈ 0.301 × log₂ n（常数可忽略）。

4. 为什么 O(log n) 高效？

对比其他复杂度（假设 n=1,000,000）：

结论：
O(log n) 几乎接近常数时间，即使 n 非常大（如 10 亿），操作次数也仅需 约 30 次（因为 log₂ 1,000,000,000 ≈ 29.9）。

5. 常见 O(log n) 的算法场景

1. 二分查找：在有序数组中查找元素。
2. 平衡二叉搜索树（如 TreeMap）：插入、删除、查找。
3. 分治算法：如快速排序的划分过程（平均 O(n log n)）。
4. 堆操作：插入、删除堆顶元素（O(log n)）。

6. 数学推导示例（二分查找）

假设数组长度为 n，最坏情况下查找次数为 x，则：

n / 2 / 2 / ... / 2 = 1  →  n / 2ˣ = 1  →  2ˣ = n  →  x = log₂ n

因此，二分查找的时间复杂度为 O(log n)。

总结

• log 默认以 2 为底，表示问题规模不断减半的次数。
• n=1000 时 log₂ n ≈ 10，因为 2¹⁰ ≈ 1000。
• O(log n) 是极其高效的时间复杂度，适用于分治策略的算法（如二分查找、平衡树操作）。

常用算法的复杂度整理

以下是常用算法的复杂度整理表格，涵盖 排序算法、查找算法、数据结构操作 等，并标注最佳、平均和最坏情况：

1. 排序算法时间复杂度

说明：

• k：桶的数量或计数范围（非比较排序算法依赖数据范围）。
• 稳定：相等元素的相对顺序是否保持不变。

2. 查找算法时间复杂度

说明：

• 哈希表的最坏情况（O(n)）发生在所有键哈希冲突时（退化为链表）。
• 二叉搜索树若不平衡（如退化成链表），查找效率降至 O(n)。

3. 数据结构操作时间复杂度

说明：

• 数组的插入/删除需移动元素（除非在末尾操作）。
• 链表的插入/删除在已知节点时为 O(1)，但查找仍需 O(n)。

4. 关键结论

1. 排序算法：
   • 最快平均时间：快速排序、归并排序、堆排序（O(n log n)）。
   • 稳定排序：归并排序、计数排序、基数排序。
2. 查找算法：
   • 哈希表 平均 O(1)，但需处理冲突。
   • 二分查找 仅适用于有序数组（O(log n)）。
3. 数据结构选择：
   • 频繁查找：用哈希表（O(1)）。
   • 有序数据：用平衡树（O(log n)）。
   • 快速插入/删除：用链表（O(1)）。

附：复杂度增长趋势对比图

n=16 时：
O(1)      → 1
O(log n)  → 4
O(n)      → 16
O(n log n)→ 64
O(n²)     → 256
O(2ⁿ)     → 65,536

掌握这些复杂度规律，可以高效选择算法和数据结构！