在复赛中，
时间复杂度极为重要。
一道题目，
可以有多种算法完成，
但是，
选用省时的算法完成题目者获得的分数高。
本文整理了时间复杂度的知识。
希望获得高分的考生必须熟练掌握。
知识点分析
1、算法复杂度是什么？
算法复杂度用来衡量算法的高效性，简单的说就是：
算法运行的有多快（时间效率）
内存占用的有多少（空间效率）
然而，运行时间和语言、机器、机器的状态、数据量的大小都有关系，不好横向比较，为此通常使用一个时间复杂度（相对度量）的概念来衡量算法有多快。
我们假设其它状态不变，仅当问题规模（数据大小）增长时，指令执行的次数也在增长，那么指令执行次数相对于问题规模来说，会构成一个函数T(n)。
例如－对于以下数组求和的算法1+2+3+…+n：
int sum = 0; //指令数为1for(int i=0; i<n; i++) sum += n; //指令数为 ncout << n; //指令数为1
显然，总的指令数为T(n) = n + 2
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))。
3、常见大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) 的例子
汉诺塔问题－代码略。
递归表达式：
将n-1个盘子从A经过C移动到B
将第n个盘子从A移动到C
将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、问题规模与算法复杂度
在noi竞赛环境，一般规定每个题目要在1秒内运行通过，而测评机每秒大概运行10^7-10^8次指令左右，因此对于问题规模n，与可通过测评的算法复杂度的对比关系大致如下：
问题规模算法复杂度
>10^7O(logn)
10^7O(n)
10^5 ~5*10^5O(nlogn)
1000 ~ 5000O(n^2)
200 ~ 500O(n^3)
20 ~ 24O(2^n)
12O(n!)
用上表做参考，可以用来：
在看到题目规模的时候，就知道大概需要选择什么算法了。
选择一个算法实现后，大概知道能通过多少测试点。
例如：一个排序的题目，30%数据<1000，50%数据<3000，100%数据<300000，则：
如果想AC(100分)，需要用O(nlogn)的算法，例如快速排序。
如果只会冒泡排序（O(n^2)），能拿到50分。
2、竞赛策略
2.1 解题
首先仔细阅读题目，通过小数据模拟理解题目，大致明白题目的输入->输出之间的逻辑。
要求-在模拟、理解试题之后，：
能自己生成更多的输入和输出样例。
能设计朴素算法来解题。
2.2 朴素算法
实现一种朴素算法，通过所有的样例，先不考虑性能。
要求：通过所有的测试样例，包括自己设计的样例，确保结果无误。
2.3 优化和复杂度理解
根据试题数据的范围，分析出复杂度分级，并对朴素算法进行优化，大致划分出不同优化方案对应的复杂度分级，以及得分范围。
要求：
根据自己的能力积累，尽可能设计出更大得分范围的优化算法。
用所有测试样例对优化算法进行测试，确保结果无误。
2.4 分支和对拍
对拍是指用脚本来调用朴素算法和优化算法两个程序，对所有输入数据做运算，比较其输出是否一致。
对拍被用来确保优化程序不会出现结果错误的情况，因为优化程序往往用到比较复杂的思路，难免编码出错。
不会对拍的情况，也可以通过对不同的数据范围实现分支控制，比如小数据调用朴素算法，大数据调用对应的优化算法，各施其责。
2.5 测试数据
为确保代码正确及性能测试通过，需要编写程序生成符合数据范围的各级测试数据，以便对优化算法进行性能测试，以及对拍所用。
复赛模拟
一、题目：最大公约数的时间复杂度
以下两种求最大公约数的方法：枚举法和辗转相除法，分别计算出时间复杂度来。
二、分析
1. 枚举法
算法描述：
取m和n的最小值，这里直接假设n<m了，下同。
循环i从n递减到1，如果i同时被n、m整除，就退出循环。
返回i
时间复杂度为O(n)
int f1(int m, int n) { int i; for(i=n; i>1; i--) if (m%i==0 && n%i==0) break; return i;}
2. 辗转相除法
算法描述：
计算r = m % n
循环：m = n, n = r, r = m%n
一直到r为0时循环结束，此时n即为最大公约数
其时间复杂度为O(logn)
int f2(int m, int n) { int r = m % n; while(r) { m = n; n = r; r = m%n; } return n;}三、扩展理解
1. 时间复杂度计算
辗转相除法每一次迭代让 m = n, n = r，即 gcd(m, n) = gcd(n, m%n) = gcd(m%n, (m%n) %n) ...
设 m = n*a + r，由于0<= r < n，于是有
m > (a+1) * r > 2 * r
而gcd(m, n) = gcd(n, r) = gcd(r, r%n)
也就是说，经过两次迭代，至少把m缩小一倍
显然算法复杂度为O(logn)
四、案例代码
#include <iostream>
using namespace std;
int f1(int m, int n) {
int i;
for(i=n; i>1; i--)
if (m%i==0 && n%i==0)
break;
return i;
}
int f2(int m, int n) {
int r = m % n;
while(r) {
m = n;
n = r;
r = m%n;
}
return n;
}
int main() {
int m=40, n =24;
cout << f1(m, n) << endl;
return 0;
}
