算法复杂度

一、算法的目标

算法是对问题的解决方案，但一个问题会有很多种算法，通常一个好的算法需要具备以下目标：

• 正确性：对合法输入、非法输入、边界输入都能正确处理，输出合理的结果。
• 可读性：算法应该描述清晰，方便阅读、理解和交流。
• 健壮性：算法应运行一致，对于相同的输入始终输出相同的结果。
• 高效性：算法应占用最少的cpu和内存得到满足的结果，这通过时间复杂度和空间复杂度进行判定。

二、算法时间复杂度

算法复杂度用来衡量算法的高效性，简单的说就是：

算法运行的有多快（时间效率）

内存占用的有多少（空间效率）

然而，运行时间和语言、机器、机器的状态、数据量的大小都有关系，不好横向比较，为此通常使用一个时间复杂度（相对度量）的概念来衡量算法有多快。

我们假设其它状态不变，仅当问题规模（数据大小）增长时，指令执行的次数也在增长，那么指令执行次数相对于问题规模来说，会构成一个函数 $T(n)$。

例如－对于以下数组求和的算法 $1+2+3+...+n：$

int sum = 0; //指令数为1
for(int i=0; i<n; i++)
  sum += n; //指令数为 n
cout << n; //指令数为1

显然，总的指令数为 $T(n) = n + 2$

三、大O函数

假设一个算法的 $T(n) = 4n^3 - 2n + 5$

当 $n$ 越来越大时，对于 $T(n)$ 增长的贡献来说，最高阶的 $n^3$ 会占据主导地位，其它项可被忽略。

例如：

$n=100$ 时，$n^3$ 是 $n$ 的的 1 万倍，因此可忽略掉后面 $n$ 的贡献。

当 $n$ 从 $100$ 变成 $1000$ 时，$n^3$ 会增长 $1000$ 倍，此时 $4n^3$ 前面的4也可被忽略。

我们一般用大O函数来表示最主要的贡献部分：$O(T(n)) = O(n^3)$，也即算法的时间复杂度。

数学定义：当存在正常数 $c$ 和某个规模 $n0$，如果对所有的 $n>=n0$，都有 $f(n) <= c T(n)$，则称 $f(n)$为T(n)的大O函数，写成：f(n) = O(T(n))。

四、常见大O函数

函数	名称	例子
O(1)	常数阶	交换算法
O(logn)	对数阶	二分查找算法
O(n)	线性阶	求和算法
O($nlogn$)	线性对数阶	快速排序算法
O($n^2$)	平方阶	冒泡排序算法
O($n^c$)	多项式阶（c>1）	多重循环的算法
O($c^n$)	指数阶	汉诺塔问题
O(n!)	阶乘阶	旅行商问题

五、扩展理解－复杂度计算与例子

1、计算方法

对算法（或代码）的指令次数进行计算组成 $T(n)$，只保留最高阶项，然后去掉最高阶项前面的常数。

例如以下代码的$T(n) = 3$, 时间复杂度为O(1)：

int a=20;
int b = a*3 + 4;
cout << b;

2、O(n)的例子

输出数组元素：

for(int i=0; i<n; i++)
  cout << a[n] << " ";

3、 O(logn)的例子

给定 n，求 2 的指数 p，使得 $p <= n < 2p$

int p = 1;
while(p < n) {
  p *= 2;
}
cout << p;

4、O($n^2$)的例子

打印二维数组：

for(int i=0; i<n; i++) {
  for(int j=0; j<n; j++)
    cout << a[i][j] << " ";
  cout << endl;
}

5、O(nlogn)的例子

for(int i=0; i<n; i++)
  for(int j=0; j<n; j *= 2)
     ...

6、O($2^n$) 的例子

汉诺塔问题－代码略。

递归表达式：

1. 将n-1个盘子从A经过C移动到B
2. 将第n个盘子从A移动到C
3. 将n-1个盘子从B经过A移动到C

显然 $T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = ....$，最高阶项为 $2^n$ ，即 O($2^n$)。

7、O(n!)的例子

旅行商问题：从一个城市出发，经过所有城市后返回出发地，求最短的路径。

如果用朴素算法，第一个城市有n种选择，第二个有n-1种选择，依次类推，复杂度为 O(n!)。

六、空间复杂度

空间复杂度指算法运行过程种临时所占用的内存大小，例如变量、数组等的开销，规则与时间复杂度一样。

1.单位换算

Byte:字节 ,bit: 二进制位

$1 B(yte) = 8 bit$

$1 KB = 1024 B$

$1 MB = 1024 KB$

$1 GB = 1024 MB$

$1 TB = 1024 GB$

2.数据类型空间大小

类型	sizeof	大致范围
int	4 B	$-2*10^9 \sim 2*10^9$
char	1 B	$0 \sim 255$
double,long long	8B	$-9*10^{18} \sim 9*10^{18}$
pointer	32位系统 4B , 64位系统 8B	-
bool	1 B

为什么不用1 bit?

因为每个数据类型都要通过指针来寻址，而系统寻址的最小单位是Byte，系统无法给一个 bit 创建指针，也无法对 bit 寻址。

分析时要注意，计算全局变量的空间复杂度要看实际运行时会用到的空间，而不是总空间，因为全局变量在未被使用时分配的是虚拟内存。

当代码里有递归函数或需要大量调用函数时，还需要分析栈空间复杂度。比如快速排序，需要递归 logn 层，因此空间复杂度是 O(logn);而归并排序在递归时每一层还需要开一个长度为 n的数组，因此空间复杂度是 nlogn。

例如：

const int N = 1E8;
int a[1000];
long long b[N];

这里的数组 a 所占用的内存空间为 $4 \times 1000 Byte \approx 4KB$，b 数组所占用的内存空间为 $8 \times 10^8 \approx 8 \times 10^5KB \approx 8 \times 10^2 MB= 800 MB$

在noi竞赛里，对于内存限制一般为128MB（或256MB），一般都足够使用。

复杂度与竞赛

1、数据范围与算法复杂度

在noi竞赛环境，一般规定每个试题要在 1 秒内运行通过，而测评机每秒大概运行 $10^7$~$10^8$ 次指令左右，因此对于给定的数据范围，与算法复杂度的对比关系大致如下：

数据范围	算法复杂度
$>10^7$	O($\log_2n$)
$10^7$	O(n)
$10^5 \sim 5*10^5$	O($n\log_2n$)
$1000 \sim 5000$	O($n^2$)
200 ~ 500	O($n^3$)
20 ~ 24	O($2^n$)
12	O($n!$)

在看到数据范围的时候，就知道大概需要选择什么算法了。 选择一个算法实现后，大概知道能通过多少测试点。 例如：一个排序的试题，30%数据<1000，50%数据<3000，100%数据<300,000，则：

如果想AC(100分)，需要用O($n\log_2n$)的算法，例如快速排序。 如果只会冒泡排序（O($n^2$)），能拿到50分。

总结下算法复杂度和算法的关系：

$n≤30$: 指数级别, dfs+剪枝，状态压缩dp

$n≤100=> O(n^3)$ : floyd，dp，高斯消元

$n≤1000=> O(n^2),O(n^2logn)$ : dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford

$n≤10^4=> O(n∗\sqrt{n})$: 块状链表、分块、莫队

$n≤10^5=> O(nlogn)$ : 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树

$n≤10^6=> O(n)$ :以及常数较小的 $O(nlogn)$ 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 $O(nlogn)$ 的做法：sort、树状数组、heap、dijkstra、spfa

$n≤10^7=> O(n)$ : 双指针扫描、kmp、AC自动机、线性筛素数

$n≤10^9=> O(\sqrt{n})$ : 判断质数

$n≤10^{18}=> O(logn)$ : 最大公约数，快速幂，数位DP

$n≤10^{1000}=> O((logn)^2)$ : 高精度加减乘除

$n≤10^{100000}=> O(logk×loglogk)$ : k表示位数表示位数，高精度加减FFT/NTT

2、竞赛策略（做题策略）

2.1 解题

仔细阅读试题，通过小数据模拟理解试题，大致明白试题的输入->输出之间的逻辑。

要求-在模拟、理解试题之后：

能提炼出试题对应的问题（去掉试题里的业务描述）

能自己生成更多的输入和输出样例(包括边界和普通情况）。

2.2 朴素算法

实现一种朴素（暴力）算法，通过所有的样例，先不考虑性能。

要求：通过所有的测试样例，包括自己设计的样例，确保结果无误。

2.3 优化和复杂度理解

根据数据的范围，分析出复杂度分级，并对朴素算法进行优化，大致划分出不同优化方案对应的复杂度分级，以及得分范围。

要求：

根据自己的能力积累，尽可能设计出更大得分范围的优化算法。

用所有测试样例对优化算法进行测试，确保结果无误。

2.4 分支和对拍

对拍是指用脚本来调用朴素算法和优化算法两个程序，对所有输入数据做运算，比较其输出是否一致。

对拍被用来确保优化程序不会出现结果错误的情况，因为优化程序往往用到比较复杂的思路，难免编码出错。

不会对拍的情况，也可以通过对不同的数据范围实现分支控制，比如小数据调用朴素算法，大数据调用对应的优化算法，各施其责。

2.5 测试数据

为确保代码正确及性能测试通过，需要编写程序生成符合数据范围的各级测试数据，以便对优化算法进行性能测试，以及对拍所用。

例题
CSPJ2022SDT1 植树节（planting）