<style> .reveal p { text-align:left; } </style> # 算法复杂度 || |:----:| || --- ## 一、算法的目标 算法是对问题的解决方案，但一个问题会有很多种算法，通常一个好的算法需要具备以下目标： - 正确性：对合法输入、非法输入、边界输入都能正确处理，输出合理的结果。 - 可读性：算法应该描述清晰，方便阅读、理解和交流。 - 健壮性：算法应运行一致，对于相同的输入始终输出相同的结果。 - 高效性：算法应占用最少的cpu和内存得到满足的结果，这通过时间复杂度和空间复杂度进行判定。 --- ## 二、算法时间复杂度 算法复杂度用来衡量算法的高效性，简单的说就是： 算法运行的有多快（时间效率） 内存占用的有多少（空间效率） 然而，运行时间和语言、机器、机器的状态、数据量的大小都有关系，不好横向比较，为此通常使用一个时间复杂度（相对度量）的概念来衡量算法有多快。 --- 我们假设其它状态不变，仅当问题规模（数据大小）增长时，指令执行的次数也在增长，那么指令执行次数相对于问题规模来说，会构成一个函数 $T(n)$。 例如－对于以下数组求和的算法 $1+2+3+...+n：$ ```c++ 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)： ```c++ int a = 20; int b = a * 3 + 4; cout << b; ``` --- ### 2、O(n)的例子 输出数组元素： ```c++ for(int i=0; i<n; i++) cout << a[i] << " "; ``` --- ### 3、 O(`$\log_2^n$`)的例子 给定 n，求 2 的指数 p，使得 $p <= n < 2p$ ```c++ int p = 1; while(p < n) { p *= 2; } cout << p; ``` --- ### 4、O($n^2$)的例子 打印二维数组： ```c++ for(int i=0; i<n; i++) { for(int j=0; j<n; j++) cout << a[i][j] << " "; cout << endl; } ``` --- ### 5、O(`$nlogn$`)的例子 ```c++ 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\times 10^9 \sim 2\times 10^9$| |char| 1 B| $0 \sim 255$ | |double,long long | 8B| $-9\times 10^{18} \sim 9\times 10^{18}$| |pointer(指针类型) | 32位系统 4B , 64位系统 8B|-| |bool | 1 B|-| --- 为什么不用1 bit? 因为每个数据类型都要通过指针来寻址，而系统寻址的最小单位是Byte，系统无法给一个 bit 创建指针，也无法对 bit 寻址。 --- 分析时要注意，计算全局变量的空间复杂度要看实际运行时会用到的空间，而不是总空间，因为全局变量在未被使用时分配的是虚拟内存。 --- 当代码里有递归函数或需要大量调用函数时，还需要分析栈空间复杂度。比如快速排序，需要递归 logn 层，因此空间复杂度是 O(logn);而归并排序在递归时每一层还需要开一个长度为 n的数组，因此空间复杂度是 nlogn。 --- 例如： ```c++ 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，则： 如果想$\color{green} 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）](http://39.99.183.126:8888/p/CSPJ2022SDT1)|