算法的定义和复杂度

算法的定义

算法，顾名思义，即计算的方法。算法通常用于解决特定的计算任务，但与可以直接在计算机上运行的程序不同，算法使用数学化的描述，更加侧重于思想，可以被看作抽象的程序。同一个算法可以有许多种不同的实现方式，两个不同的程序里也可能使用了同一种算法。

本章介绍一些基础算法。当一个计算任务足够通用，在各种问题中广泛出现时，解决该任务的算法就会被更多的算法所调用，拥有相当的重要性和基础性。同时，越通用的算法，通常越是简洁，越近似于思想而非程序。

算法的复杂度

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

时间复杂度和空间复杂度的概念

时间复杂度

在信息学奥赛里，当我们编写程序解决问题时，程序运行需要一定的时间。时间复杂度就是用来估算程序运行时间随着输入数据规模增大而增长的速度。它不表示具体的运行时间，而是一种趋势。

打个比方，假如你要在一堆书里找一本特定的书。如果书是随便乱放的，你就得一本一本地找，书越多，找的时间就越长。要是书是按顺序排列好的，你就可以用更快的方法去找，比如二分查找。这两种方法随着书的数量增多，找书所花的时间增长速度是不一样的，时间复杂度就是描述这种增长速度的。

常见的时间复杂度有：

• $O(1)$：无论输入数据规模多大，程序运行时间都不变。就像你从口袋里拿出钥匙，不管口袋里东西多还是少，拿钥匙的时间差不多。
• $O(n)$：程序运行时间和输入数据规模 $n$ 成正比。比如你要数一堆苹果，苹果越多，数的时间就越长，而且是线性增长的。
• $O(n^2)$：程序运行时间和输入数据规模 $n$ 的平方成正比。如果 $n$ 翻倍，运行时间会变成原来的 4 倍。这就好像你要比较教室里每两个同学的身高，同学越多，比较的次数就会大幅增加。

空间复杂度

空间复杂度是用来估算程序运行时所需要的额外存储空间随着输入数据规模增大而增长的速度。

还是用找书的例子，如果你找书的时候需要额外的笔记本记录每本书的位置，书越多，笔记本需要的页数就越多，这就是空间复杂度的概念。

常见的空间复杂度有：

• $O(1)$：无论输入数据规模多大，程序所需要的额外存储空间都不变。
• $O(n)$：程序所需要的额外存储空间和输入数据规模 $n$ 成正比。

代码演示

$O(1)$ 时间复杂度和 $O(1)$ 空间复杂度

#include <iostream>
using namespace std;
 
int main() {
    int a;
    cin >> a;  // 读入一个整数
    int b = a + 1;  // 进行一次加法运算
    cout << b << endl;  // 输出结果
    return 0;
}

• 时间复杂度分析：这个程序只进行了一次读入、一次加法运算和一次输出，无论输入的整数 $a$ 是多大，程序执行的步骤都是固定的，所以时间复杂度是 $O(1)$。
• 空间复杂度分析：程序只使用了两个额外的整数变量 $a$ 和 $b$，无论输入数据规模如何变化，所需要的额外存储空间都是固定的，所以空间复杂度是 $O(1)$。

$O(n)$ 时间复杂度和 $O(1)$ 空间复杂度

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;  // 读入数据规模
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;  // 读入一个数
        sum = sum + num;  // 累加
    }
    cout << sum << endl;  // 输出总和
    return 0;
}

• 时间复杂度分析：程序中有一个 for 循环，循环次数是 $n$，每次循环执行一次读入和一次加法运算，所以程序的运行时间和输入数据规模 $n$ 成正比，时间复杂度是 $O(n)$。
• 空间复杂度分析：程序只使用了几个额外的整数变量，如 $n$、sum 和 num，无论输入数据规模 $n$ 有多大，所需要的额外存储空间都是固定的，所以空间复杂度是 $O(1)$。

$O(n^2)$ 时间复杂度和 $O(1)$ 空间复杂度

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;  // 读入数据规模
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << i * j << " ";  // 输出乘积
        }
        cout << endl;
    }
    return 0;
}

• 时间复杂度分析：程序中有两层嵌套的 for 循环，外层循环执行 $n$ 次，内层循环也执行 $n$ 次，所以总的执行次数是 $n\times n=n^2$，时间复杂度是 $O(n^2)$。
• 空间复杂度分析：程序只使用了几个额外的整数变量，如 $n$、$i$ 和 $j$，无论输入数据规模 $n$ 有多大，所需要的额外存储空间都是固定的，所以空间复杂度是 $O(1)$。

复杂度进阶（初学者可忽略）

基本操作数

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

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

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

时间复杂度

定义

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

引入

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

1. 现代计算机每秒可以处理数亿乃至更多次基本运算，因此我们处理的数据规模通常很大。如果算法 A 在规模为 $n$ 的数据上用时为 $100n$ 而算法 B 在规模为 $n$ 的数据上用时为 $n^2$，在数据规模小于 $100$ 时算法 B 用时更短，但在一秒钟内算法 A 可以处理数百万规模的数据，而算法 B 只能处理数万规模的数据。在允许算法执行时间更久时，时间复杂度对可处理数据规模的影响就会更加明显，远大于同一数据规模下用时的影响。
2. 我们采用基本操作数来表示算法的用时，而不同的基本操作实际用时是不同的，例如加减法的用时远小于除法的用时。计算时间复杂度而忽略不同基本操作之间的区别以及一次基本操作与十次基本操作之间的区别，可以消除基本操作间用时不同的影响。

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

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

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

渐进符号的定义

渐进符号是函数的阶的规范描述。简单来说，渐进符号忽略了一个函数中增长较慢的部分以及各项的系数（在时间复杂度相关分析中，系数一般被称作「常数」），而保留了可以用来表明该函数增长趋势的重要部分。

一个简单的记忆方法是，含等于（非严格）用大写，不含等于（严格）用小写，相等是 $\Theta$，小于是 $O$，大于是 $\Omega$。大 $O$ 和小 $o$ 原本是希腊字母 Omicron，由于字形相同，也可以理解为拉丁字母的大 $O$ 和小 $o$。

在英文中，词根「-micro-」和「-mega-」常用于表示 10 的负六次方（百万分之一）和六次方（百万），也表示「小」和「大」。小和大也是希腊字母 Omicron 和 Omega 常表示的含义。

大 Θ 符号

对于函数 $f(n)$ 和 $g(n)$，$f(n)=\Theta(g(n))$，当且仅当 $\exists c_1,c_2,n_0>0$，使得 $\forall n \ge n_0, 0\le c_1\cdot g(n)\le f(n) \le c_2\cdot g(n)$。

也就是说，如果函数 $f(n)=\Theta(g(n))$，那么我们能找到两个正数 $c_1, c_2$ 使得 $f(n)$ 被 $c_1\cdot g(n)$ 和 $c_2\cdot g(n)$ 夹在中间。

例如，$3n^2+5n-3=\Theta(n^2)$, 这里的 $c_1, c_2, n_0$ 可以分别是 $2, 4, 100$。$n\sqrt {n} + n{\log^5 n} + m{\log m} +nm=\Theta(n\sqrt {n} + m{\log m} + nm)$，这里的 $c_1, c_2, n_0$ 可以分别是 $1, 2, 100$。

大 O 符号

$\Theta$ 符号同时给了我们一个函数的上下界，如果只知道一个函数的渐进上界而不知道其渐进下界，可以使用 $O$ 符号。$f(n)=O(g(n))$，当且仅当 $\exists c,n_0$，使得 $\forall n \ge n_0,0\le f(n)\le c\cdot g(n)$。

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

需要注意的是，这里的「上界」和「下界」是对于函数的变化趋势而言的，而不是对算法而言的。算法用时的上界对应的是「最坏时间复杂度」而非大 $O$ 记号。所以，使用 $\Theta$ 记号表示最坏时间复杂度是完全可行的，甚至可以说 $\Theta$ 比 $O$ 更加精确，而使用 $O$ 记号的主要原因，一是我们有时只能证明时间复杂度的上界而无法证明其下界（这种情况一般出现在较为复杂的算法以及复杂度分析），二是 $O$ 在电脑上输入更方便一些。

大 Ω 符号

同样的，我们使用 $\Omega$ 符号来描述一个函数的渐进下界。$f(n)=\Omega(g(n))$，当且仅当 $\exists c,n_0$，使得 $\forall n \ge n_0,0\le c\cdot g(n)\le f(n)$。

小 o 符号

如果说 $O$ 符号相当于小于等于号，那么 $o$ 符号就相当于小于号。

小 $o$ 符号大量应用于数学分析中，函数在某点处的泰勒展开式拥有皮亚诺余项，使用小 $o$ 符号表示严格小于，从而进行等价无穷小的渐进分析。

$f(n)=o(g(n))$，当且仅当对于任意给定的正数 $c$，$\exists n_0$，使得 $\forall n \ge n_0,0\le f(n)< c\cdot g(n)$。

小 ω 符号

如果说 $\Omega$ 符号相当于大于等于号，那么 $\omega$ 符号就相当于大于号。

$f(n)=\omega(g(n))$，当且仅当对于任意给定的正数 $c$，$\exists n_0$，使得 $\forall n \ge n_0,0\le c\cdot g(n)< f(n)$。

常见性质

• $f(n) = \Theta(g(n))\iff f(n)=O(g(n))\land f(n)=\Omega(g(n))$
• $f_1(n) + f_2(n) = O(\max(f_1(n), f_2(n)))$
• $f_1(n) \times f_2(n) = O(f_1(n) \times f_2(n))$
• $\forall a \neq 1, \log_a{n} = O(\log_2 n)$。由换底公式可以得知，任何对数函数无论底数为何，都具有相同的增长率，因此渐进时间复杂度中对数的底数一般省略不写。

简单的时间复杂度计算的例子

for 循环

int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
    for (int k = 0; k < m; ++k) {
      cout << "hello world\n";
    }
  }
}

如果以输入的数值 $n$ 和 $m$ 的大小作为数据规模，则上面这段代码的时间复杂度为 $\Theta(n^2m)$。

DFS

在对一张 $n$ 个点 $m$ 条边的图进行DFS时，由于每个节点和每条边都只会被访问常数次，复杂度为 $\Theta(n+m)$。

哪些量是常量？

当我们要进行若干次操作时，如何判断这若干次操作是否影响时间复杂度呢？例如：

const int N = 100000;
for (int i = 0; i < N; ++i) {
  cout << "hello world\n";
}

如果 $N$ 的大小不被看作输入规模，那么这段代码的时间复杂度就是 $O(1)$。

进行时间复杂度计算时，哪些变量被视作输入规模是很重要的，而所有和输入规模无关的量都被视作常量，计算复杂度时可当作 $1$ 来处理。

需要注意的是，在进行时间复杂度相关的理论性讨论时，「算法能够解决任何规模的问题」是一个基本假设（当然，在实际中，由于时间和存储空间有限，无法解决规模过大的问题）。因此，能在常量时间内解决数据规模有限的问题（例如，对于数据范围内的每个可能输入预先计算出答案）并不能使一个算法的时间复杂度变为 $O(1)$。

空间复杂度

类似地，算法所使用的空间随输入规模变化的趋势可以用 空间复杂度 来衡量。

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= n; j++) {
    cout<<"hello";
  }
}