CS
登录

Time Complexity

时间复杂度（Time Complexity）

1. 核心概念：什么是时间复杂度？

时间复杂度是衡量算法执行操作数量的指标，用于分析算法随输入规模（通常用n表示）增长时，操作次数的变化趋势。在编程竞赛中，算法需在规定时间内运行完成，例如：

  • USACO 中，C++ 提交时限为 2 秒，Java/Python 提交时限为 4 秒。

  • 评分服务器的保守运算能力估算为 每秒 10^8 次操作，优化后可接近每秒 5×10^8 次操作（取决于常数因子）。

2. 复杂度计算（Complexity Calculations）

时间复杂度通过大O符号（Big O Notation） 表示，聚焦“最坏情况”下的操作次数，且忽略常数因子和低阶项。以下是具体计算规则及示例（默认循环内部代码为 O(1)，即常数时间操作）：

2.1 常数时间：O(1)

执行固定数量的操作，与输入规模n无关。

示例：变量声明、赋值、简单算术运算，以及输入输出操作。

int a = 5;
int b = 7;
int c = 4;
int d = a + b + c + 153; // 固定4次加法，无循环/输入依赖

2.2 线性时间：O(n)

操作次数与输入规模n成线性关系，即循环执行n次（或k*n + b次，k、b为常数，常数因子和低阶项被忽略）。

示例1：for循环

for (int i = 1; i <= n; i++) {
    // 常数时间代码
}

示例2：while循环

int i = 0;
while (i < n) {
    // 常数时间代码
    i++; // 循环执行n次
}

示例3：含常数因子的线性循环（仍为 O(n)）

for (int i = 1; i <= 5*n + 17; i++) { // 5*n和+17被忽略
    // 常数时间代码
}

2.3 嵌套循环：乘法原则

嵌套循环的时间复杂度为各层循环复杂度的乘积（取最坏情况）。

  • 示例1：O(nm)（外层O(n)，内层O(m)）

  for (int i = 1; i <= n; i++) { // 外层n次
      for (int j = 1; j <= m; j++) { // 内层m次
          // 常数时间代码
      }
  }

  • 示例2：O(n²)（外层O(n)，内层最坏O(n)）

  for (int i = 1; i <= n; i++) { // 外层n次
      for (int j = i; j <= n; j++) { // 内层最坏n次（i=1时）
          // 常数时间代码
      }
  }

2.4 多代码块：取最坏/求和原则

  • 若多个块独立，复杂度取最坏情况（即最高阶项）。

示例：O(n²)（忽略低阶的O(n)块）

  // 块1：O(n²)
  for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) { /* 常数代码 */ }
  }
  // 块2：O(n)（低阶，被忽略）
  for (int i = 1; i <= n + 58834; i++) { /* 常数代码 */ }

  • 若块的变量独立（如n和m），复杂度为各块复杂度之和。

示例：O(n² + m)（n和m无关，无法忽略任一阶）

  // 块1：O(n²)
  for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) { /* 常数代码 */ }
  }
  // 块2：O(m)
  for (int i = 1; i <= m; i++) { /* 常数代码 */ }

3. 常见复杂度与约束（Common Complexities and Constraints）

不同算法/数据结构对应固定的时间复杂度，且输入规模n的上限决定了可行的复杂度。

3.1 常见算法/数据结构的复杂度

操作/算法/数据结构

时间复杂度

说明

数学公式计算（直接求结果）

O(1)

无循环，直接通过公式得出答案

二分查找

O(log n)

每次缩小一半范围，对数级增长

有序集合/映射（如C++ set/map）、优先队列

O(log n) 每操作

插入、删除、查询等单操作的复杂度

朴素质因数分解/素数判断

O(√n)

遍历到√n即可判断素数或分解因数

读取n个输入项/遍历n元素数组

O(n)

线性遍历，与n成正比

排序（归并排序、Collections.sort）

O(n log n)

大多数默认排序算法的复杂度

Java Arrays.sort（基本类型）

O(n²)

底层为快速排序，最坏情况为平方级（参考数据结构入门章节）

遍历k大小子集（如三元组）

O(n^k)

如遍历所有三元组为 O(n³)

遍历所有子集

O(2^n)

每个元素有“选”或“不选”两种可能，指数级增长

遍历所有排列

O(n!)

全排列数量为n的阶乘，阶乘级增长（复杂度极高）

3.2 输入规模

下表为保守上限（实际可略高，但可快速判断算法是否可行）：

输入规模n上限

可行的时间复杂度

$n ≤ 10$

$O(n!)、O(n^7)、O(n^6)$

$n ≤ 20$

$O(2^n · n)、O(n^5)$

$n ≤ 80$

$O(n^4)$

$n ≤ 400$

$O(n^3)$

$n ≤ 7500$

$O(n²)$

$n ≤ 7×10^4$

$O(n\sqrt{n})$

$n ≤ 5×10^5$

$O(n log n)$

$n ≤ 5×10^6$

$O(n)$

$n ≤ 10^18$

$O(log²n)、O(log n)、O(1)$

注意：USACO Bronze 级题目常出现n ≤ 100，此时复杂度可能为 O(n)（而非更高阶），需结合题目具体分析。

4. 常数因子（Constant Factor）

4.1 定义

常数因子指相同复杂度的操作，实际执行时间的差异。例如：

  • 3次加法比1次加法耗时略长；

  • 数组二分查找（O(log n)）比有序集合插入（O(log n)）更快。

4.2 大O符号的处理

大O符号完全忽略常数因子，但在时间限制严格时，常数因子可能导致“超时（TLE）”。此时需优化常数因子，例如：

  • 遍历“有序三元组”（O(n³)）可优化为遍历“无序三元组”，减少6倍操作（因有序三元组有6种排列，无序仅1种）。

建议：初期无需过度优化常数因子，只需了解其存在即可。

5. 大O符号的正式定义（Formal Definition of Big O Notation）

设f(n)和g(n)为从非负实数到非负实数的函数。若存在正常数n₀和c，使得当n ≥ n₀时，f(n) ≤ c·g(n)，则称f(n) = O(g(n))。

关键推论

  • 一个线性函数（如 O(n)）也可表示为 O(n/2)、O(2n)、O(n²) 等，但通常取最简洁、约束最强的形式（即 O(n)）。

6. 扩展：P vs. NP（可选）

概念

定义

P类问题

可在多项式时间（如 O(n²)、O(n³)、O(n^100)）内解决的问题。

NP类问题

解决方案可在多项式时间内验证的问题（“NP”=Non-deterministic Polynomial）。

示例与未解决问题

  • NP类问题示例：广义数独（验证一个解是否正确需多项式时间，但求解是否能在多项式时间内完成未知）。

  • “P vs. NP”问题：是否所有NP类问题都属于P类（即“可验证”是否等价于“可多项式时间解决”）？这是计算机科学领域的经典未解决问题。

7. 测试题（Quiz）

CS
登录