---
title: "复杂度预估"
description: "竞赛技巧与复杂度估算等实战经验。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 复杂度预估

![](https://img.dailyup.xyz/originals/8208462192513-2b827122-608b-4c0e-be2a-575a03159f1f.png)

在算法竞赛中，根据题目给出的数据范围来预估所需的算法复杂度是一项关键技能，这能帮助你在编写代码前就判断所选择的解法是否可行，避免超过（TLE）。
## 计算量与时间限制

### 时间限制

算法竞赛中，对每道题目的运行时间都有一个上限，通常是 1 秒或 2 秒，这是我们判断是否超时的基准。

### 评测机计算能力估算

什么是基本运算？一般来说，加减乘除、位运算、比较、赋值、数组访问等，都可以近似看作为一次基本运算。

现代计算机的 CPU **每秒大约能执行 $10^8$（ 1 亿）次基本运算**，这是一个非常重要的经验值！

而且在实际竞赛环境中，应该会**更保守一点**，可以按每秒钟能执行 $10^6$ 次基本运算为基准。如果你的解法涉及到计算次数超过这个数量，执行时间就会超过 1 秒，而如果题目所要求的时间限制是 1 秒，就会出现超时（TLE）错误，评测就通不过。

我们的目标就是：根据题目给出的最大输入规模 $N$（或其它变量），选择一个时间复杂度，该复杂度的计算结果大致在 $10^6$ 这个数量级或更小。
## 常见时间复杂度处理规模

以下是不同时间复杂度在常规竞赛环境（约1秒时间限制）下能处理的数据量参考（经验法则）：

|时间复杂度|可处理数据规模（n）|典型算法举例|
|---|---|---|
|O(1)|任意大小|数学公式计算|
|O(log n)|~10¹⁸|二分查找、快速幂|
|O(n)|~10⁷|线性遍历、前缀和|
|O(n log n)|~10⁵ - 10⁶|快速排序、归并排序|
|O(n²)|~10³ - 5×10³|冒泡排序、朴素DP|
|O(n³)|~100 - 500|Floyd算法、三维DP|
|O(2ⁿ)|~20 - 25|子集枚举、暴力回溯|
|O(n!)|~10 - 12|全排列生成|

## 如何根据数据范围选择算法

举个例子，如果题目给出的数据范围是：$n \le 10^6$。

参考上面的常见时间复杂度处理规模表，如果选择的算法复杂度在 $O(n log n)$ 以内，包括 $O(1)$、$O(log n)$ 、$O(n)$ 以及 $O(n log n)$ ，都是可行的。但如果选择的算法复杂度为 $O(n^2)$，要保证程序执行时间在 1 秒以内，可处理的数据规模不能超过 $10^3$，而我们这里的数据范围（$10^6$）远超了，肯定会超时。

同样的，如果有多个变量，如果 $n$ 和 $m$，若 $n \le 10^6$，$m \le 10^6$
- $O(n + m)$ → 可行
- $O(n \times m)$  → 不可行

记住，当 $n \ge 10^6$  时，$O(n^2)$ 复杂度的算法几乎都是通不过的（也就是普通的嵌套循环），必须寻求更优解。


## 实战练习

通过一个练习来看看，数据范围如何影响到算法的选择。

给定一整数 $n$ ，要求找出所的质数。

求质数，我们学过很多方法，还记吧？

> 在算法竞赛中，质数判断和生成是非常基础，但很重要的问题，大家需要非常熟悉，不仅熟悉写法，还需要熟悉不同求解方法的复杂度。
### 朴素解法

朴素解法源于质数的定义 -- 只能被 1 和它本身整除的数。

朴素解法的代码实现：

```cpp
#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if(n <= 1) return false;
    for(int i = 2; i*i <= n; i++) {  // 只需检查到√n
        if(n % i == 0) return false;
    }
    return true;
}

int main() {
    int num = 17;
    if(isPrime(num)) {
        cout << num << "是质数" << endl;
    } else {
        cout << num << "不是质数" << endl;
    }
    return 0;
}
```

算法复杂度为 $O(\sqrt n)$ ，当 $n$ 较小时（如 $n \le 10^6$） 可以接受，因此适合单个数的质数判断，但不适用于大规模质数筛选。
### 埃氏筛法

该算法来自古希腊数学家埃拉托斯特尼，又称埃拉托斯特尼筛法，其基本思想是通过 “筛除” 所有非质数来找出质数。

步骤如下：
1. 从 2 开始，将所有倍数标记为非质数
2. 下一个未被标记的数就是质数
3. 重复这个过程

参考代码如下：

```cpp
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e6+5;
bool isPrime[MAX];

void sieve() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i*i <= MAX; i++) {
        if(isPrime[i]) {
            for(int j = i*i; j <= MAX; j += i) {  // 从i²开始标记
                isPrime[j] = false;
            }
        }
    }
}

int main() {
    sieve();
    for(int i = 2; i <= 100; i++) {
        if(isPrime[i]) cout << i << " ";
    }
    return 0;
}
```

该算法的关键优化点在于，从 $i^2$ 开始标记（因为更小的倍数已经被更小的质数标记过了），算法时间复杂度为：$O(n log log n)$，近似线性复杂度，比朴素方法快很多。

适用于中等规模预处理（ $n \le 10^7$ ）情况。
### 线性筛

线性筛改进自埃氏筛，由欧拉提出，因此又称欧拉筛，在埃氏筛的基础上进一步优化，确保每个合数只被它的最小质因数筛掉一次，达到真正的线性时间复杂度。

```cpp
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e6+5;
bool isPrime[MAX];
vector<int> primes;  // 存储所有质数

void linearSieve() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i <= MAX; i++) {
        if(isPrime[i]) {
            primes.push_back(i);
        }
        for(int j = 0; j < primes.size() && i*primes[j] <= MAX; j++) {
            isPrime[i*primes[j]] = false;
            if(i % primes[j] == 0) break;  // 关键优化
        }
    }
}

int main() {
    linearSieve();
    cout << "1e6以内的质数个数: " << primes.size() << endl;
    return 0;
}
```

关键优化点：
- `if(i % primes[j] == 0) break`：确保每个合数只被最小质因数筛一次
- 同时生成质数列表和标记非质数

在竞赛中，线性筛是首选，尤其是需要处理数论相关问题。

## 总结

根据数据范围预估复杂度是算法竞赛中的一项基本功，能帮你：

1. **快速筛选可行算法：** 排除掉那些明显会超时的思路。
2. **确定优化方向：** 如果当前思路复杂度过高，就知道必须寻找更高效的算法或数据结构。
3. **理解出题人意图：** 数据范围往往强烈暗示了题目考察的知识点（例如 N ≤ 20 很可能考状压 DP 或搜索，N ≤ 10^5 很可能考 O(N log N) 或 O(N)）。

Source: https://cppguide.xyz/competition/estimation/index.mdx