复赛准备：知道这个知识点至少多得50分！

在复赛中，

时间复杂度极为重要。

一道题目，

可以有多种算法完成，

但是，

选用省时的算法完成题目者获得的分数高。

本文整理了时间复杂度的知识。

希望获得高分的考生必须熟练掌握。

知识点分析

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) 的例子

汉诺塔问题－代码略。

递归表达式：

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、问题规模与算法复杂度

在noi竞赛环境，一般规定每个题目要在1秒内运行通过，而测评机每秒大概运行10^7-10^8次指令左右，因此对于问题规模n，与可通过测评的算法复杂度的对比关系大致如下：

问题规模	算法复杂度
>10^7	O(logn)
10^7	O(n)
10^5 ~5*10^5	O(nlogn)
1000 ~ 5000	O(n^2)
200 ~ 500	O(n^3)
20 ~ 24	O(2^n)
12	O(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;

}

---