#复杂度预估

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

#计算量与时间限制

#时间限制

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

#评测机计算能力估算

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

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

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

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

#常见时间复杂度处理规模

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

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

举个例子，如果题目给出的数据范围是：$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 和它本身整除的数。

朴素解法的代码实现：

#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. 重复这个过程

参考代码如下：

#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$ ）情况。

#线性筛

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

#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)）。