复杂度

复杂度简介

时间复杂度和空间复杂度是衡量一个算法效率的重要标准。

基本操作数

同一个算法在不同的计算机上运行的速度会有一定的差别，并且实际运行速度难以在理论上进行计算，实际去测量又比较麻烦，所以我们通常考虑的不是算法运行的实际用时，而是算法运行所需要进行的基本操作的数量。

在普通的计算机上，加减乘除、访问变量（基本数据类型的变量，下同）、给变量赋值等都可以看作基本操作。

对基本操作的计数或是估测可以作为评判算法用时的指标。

时间复杂度

定义

衡量一个算法的快慢，一定要考虑数据规模的大小。所谓数据规模，一般指输入的数字个数、输入中给出的图的点数与边数等等。一般来说，数据规模越大，算法的用时就越长。而在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即 时间复杂度。

引入

考虑用时随数据规模变化的趋势的主要原因有以下几点：

• 现代计算机每秒可以处理数亿乃至更多次基本运算，因此我们处理的数据规模通常很大。

  • 如果算法 $A$ 在规模为 $n$ 的数据上用时为 $100n$
  • 算法 $B$ 在规模为 $n$ 的数据上用时为 $n^2$
  • 在数据规模小于 $100$ 时算法 $B$ 用时更短，但在一秒钟内算法 $A$ 可以处理数百万规模的数据，而算法 $B$ 只能处理数万规模的数据。在允许算法执行时间更久时，时间复杂度对可处理数据规模的影响就会更加明显，远大于同一数据规模下用时的影响。
  • 这就是时间复杂度的价值：它揭示了算法在「大规模数据」下的表现。

• 我们采用基本操作数来表示算法的用时，而不同的基本操作实际用时是不同的，例如加减法的用时远小于除法的用时。计算时间复杂度而忽略不同基本操作之间的区别以及一次基本操作与十次基本操作之间的区别，可以消除基本操作间用时不同的影响。

当然，算法的运行用时并非完全由输入规模决定，而是也与输入的内容相关。所以，时间复杂度又分为几种，例如：

• 最坏时间复杂度：即每个输入规模下用时最长的输入对应的时间复杂度。在算法竞赛中，由于输入可以在给定的数据范围内任意给定，我们为保证算法能够通过某个数据范围内的任何数据，一般考虑最坏时间复杂度。
• 平均（期望）时间复杂度：即每个输入规模下所有可能输入对应用时的平均值的复杂度（随机输入下期望用时的复杂度）。

所谓「用时随数据规模而增长的趋势」是一个模糊的概念，我们需要借助下文所介绍的 渐进符号 来形式化地表示时间复杂度。

渐进符号的定义

大 O 符号

研究时间复杂度时通常会使用 $O$ 符号，因为我们关注的通常是程序用时的 上界，而不关心其用时的 下界。

或者说在最坏情况下，程序的用时情况。

时间复杂度的计算准则

• 只考虑与输入规模有关的变量：如 $n, m$ 等。
• 忽略常数和系数：如 $2n$、$n+100$ 均为 $O(n)$。
• 只保留最高次项：如 $n^3 + n^2 + n$ 的复杂度为 $O(n^3)$。

例子

例子：三层循环嵌套

若输入规模为 $n$ 和 $m$，以下代码的时间复杂度为 $O(n^2m)$。

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= m; k++)
            cout << "helloworld\n";

---

例子：固定次数循环

若 $k$ 为常数，代码的时间复杂度为 $O(1)$。

int k = 10000;
for (int i = 1; i <= k; i++)
    cout << "helloworld\n";

---

例子：区间乘积求和

输入一个长度为 $n$ 的数组，计算所有满足 $i \leq j$ 的 $a[i] \cdot a[j]$ 之和。

cin >> n;
for (int i = 1; i <= n; i++)
    cin >> a[i];

sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
        sum += a[i] * a[j];

cout << sum;

• 输入数组：$\texttt{cin >> a[i]}$ 执行了 $n$ 次，时间复杂度为 $O(n)$。
• 双重循环计算乘积之和：

\[ n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2} \]

• 时间复杂度为 $O(n^2)$。
• 总时间复杂度：$O(n) + O(n^2) = O(n^2)$

只保留最高次项并忽略常数，最终复杂度为：$O(n^2)$

---

例子：判断质数

只需判断 $2$ 到 $\sqrt{x}$ 的因子，最多循环 $\sqrt{x}$ 次。

时间复杂度：$O(\sqrt{x})$

bool prime(int x) 
{
    if (x <= 1) return 0;
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0)
            return 0;
    return 1;
}

---

对数简介

若 $a^x = n$，其中 $a > 0$ 且 $a \ne 1$，则 $x$ 叫做以 $a$ 为底的 $n$ 的对数，记作：

\[ x = \log_a n \]

其中，$a$ 是底数，$n$ 是真数。

• $2^3 = 8 \Rightarrow \log_2 8 = 3$
• $10^2 = 100 \Rightarrow \log_{10} 100 = 2$，也可写作 $\lg 100 = 2$

算法中的应用

由于对数底数之间可通过换底公式转换（如 $\log_a b = \frac{\log_c b}{\log_c a}$），所以在时间复杂度中，通常忽略底数，统一写作 $O(\log n)$。

---

例子：数位拆分

数位拆分以及进制转换属于对数复杂度，为 $O(\log{n})$。

while (n)
{
    cout << n % 10 << " ";
    n /= 10;
}

---

例子：二进制下有几个 $1$

时间复杂度：$O(\log{x})$。

int count(long long x) 
{
    int num = 0;
    while (x) 
    {
        if (x % 2 == 1) num++;
        x /= 2;
    }
    return num;
}

如何判断超时

一台计算机每秒大约能完成 $10^8$ 次基本操作。

假设给定的程序的时间复杂度为 $O(n^2)$，而 $n$ 最坏情况下为 $10^6$ 时，程序最坏的计算次数为 $(10^6)^2=10^{12}$。

而一秒只能完成大约 $10^8$ 次基本操作，因此该程序一定会超时。

这也揭示了学习时间复杂度的意义，我们不需要通过评测机评测，仅仅通过对时间复杂度的分析即可知道自己是否超时或者说能够得到多少分。

举个例子

这是 [CSP-S 2024] 第三题的数据范围及测试点说明：

测试点	$n$	$A_i$
$1\sim 4$	$\leq 15$	$\leq 15$
$5\sim 7$	$\leq 10^2$	$\leq 10^2$
$8\sim 10$	$\leq 2000$	$\leq 2000$
$11,12$	$\leq 2\times 10^4$	$\leq 10^6$
$13\sim 15$	$\leq 2\times 10^5$	$\leq 10$
$16\sim 20$	$\leq 2\times 10^5$	$\leq 10^6$

• 假设你设计了一个时间复杂度为 $O(n^2)$ 的且正确的算法，那么你可以通过前 $10$ 个测试点而得到 $50$ 分。

• 假设你设计了一个时间复杂度为 $O(n)$ 的且正确的算法，那么你可以通过前 $20$ 个测试点而得到 $100$ 分。

---

常见的时间复杂度

时间复杂度	复杂度描述	可以通过的数据范围
$O(1)$	常数时间复杂度，算法的运行时间不随输入规模变化。	$n$ 可以无限大
$O(\log n)$	对数时间复杂度。	$n\leq 10^{18}$
$O(n)$	线性时间复杂度。	$n\leq 10^{8}$
$O(n \log n)$	线性对数时间复杂度，通常出现在排序算法中。	$n\leq 2\times 10^6$
$O(n^2)$	平方时间复杂度，通常出现在简单排序算法或双重循环中。	$n\leq 5000$
$O(n^3)$	立方时间复杂度，通常出现在三重循环中。	$n\leq 500$
$O(2^n)$	指数时间复杂度。	$n\leq 20$
$O(n!)$	阶乘时间复杂度。	$n\leq 10$

---

空间复杂度

除了时间复杂度外，我们也关心程序使用的内存随输入规模变化的趋势，这被称为 空间复杂度。

空间复杂度通常不需要精确分析，但在面对题目的空间限制时，需要学会判断：

• 所使用的数据结构是否会超出限制？

常见类型的空间

• 位：1 bit 是计算机存储的最小单位，通常表示为 $0$ 或 $1$。
• 字节：1 byte = 8 bit，计算机存储的基本单位。
• 千字节：1 KB = 1024 bytes
• 兆字节：1 MB = 1024 KB
• 千兆字节：1 GB = 1024 MB

类型	字节
int	$4$
long long	$8$
float	$4$
double	$8$
char	$1$
bool	$1$

内存计算

• 题目限制空间为 $\textbf{256MB}$，某同学定义了一个大小为 $10^9$ 的 $\texttt{int}$ 数组。

该数组占用空间为：

\[ 4 \times 10^9\,\text{B} = \frac{4 \times 10^9}{1024^2} \approx 3814\,\text{MB} > 256\,\text{MB} \]

结论： 严重超出内存限制，会直接 $\texttt{MLE（Memory Limit Exceeded）}$，甚至无法运行。

---

空间的使用必须谨慎。曾有学生在 CSP-J 第一题中因数组空间开大导致程序无法运行，痛失满分。

• 大数组请计算大小，确认是否在限制内。

总结

分析时间与空间复杂度，是解决算法题的基本功。

• 提交前评估时间复杂度，确认不会 TLE。
• 判断是否存在大数组/递归栈爆炸的风险。
• 即使无法 AC，也能根据数据范围拿到部分分。