复杂度

CPU 很快，但不够快。

复杂度

具体衡量、比较算法优劣的指标有以下两个：

1. 空间复杂度 $S(n)$，程序在执行时所需要的存储空间大小，这个大小往往和输入规模 $n$ 有关。空间复杂度过大的算法需要大量的资源，你得买更多的内存条或硬盘。
2. 时间复杂度 $T(n)$，程序在执行时所耗费的时间长度，也和输入规模 $n$ 有关。时间复杂度过大的算法可能导致我们有生之年都看不到结果。

当你在 OJ 的程序无法在规定时间内返回答案时，网站便会返回 TLE（时间超限）；如果申请了超过限制的内存，网站会返回 RE（运行异常） 或 MLE（内存超限）。

在分析算法效率时，经常关注两种复杂度

• 最坏情况复杂度 $T_{\text{worst}}(n)$；
• 平均复杂度 $T_{\text{avg}}(n)$。

比如当我们在书架上顺序查找一本书时，最好的情况是一次找到，最坏的情况是查遍了 $n$ 本书才找到，此时最坏复杂度就是 $C\cdot n$。平均查找次数要更麻烦一点，计算期望要对每种可能及概率求和。

对 $T_{\text{worst}}(n)$ 进行分析往往比 $T_{\text{avg}}(n)$ 容易，因为大多数时候定义“平均”不是一件容易的事。

渐进表示法

精确的比较程序执行的步数是没有意义的，因为每一步执行时间可能不同；对计算资源进行完整的分析太繁琐，也无法捕捉到关键信息。

所以在比较算法优劣时，一般只考虑宏观性质，即当输入规模 $n$ 充分大时，我们观察不同算法复杂度的增长趋势，来断定哪种算法效率更高。

为此引入数学中的渐进符号：

• 如果存在常数 $C>0,n_0>0$，使得当 $n⩾n_0$ 时有 $T(n)⩽Cf(n)$，则称 $T(n)\in O(f(n))$。
• 如果存在常数 $C>0,n_0>0$，使得当 $n⩾n_0$ 时有 $T(n)⩾Cf(n)$，则称 $T(n)\in \mathrm{\Omega }(f(n))$。
• 如果存在 $T(n)\in \mathrm{\Omega }(f(n))$ 同时 $T\in O(f(n))$，则称 $T(n)\in \mathrm{\Theta }(f(n))$。

我们一般分别称 $O(\cdot ),\mathrm{\Omega }$ 为算法的上下界，但需要注意一个函数可能有很多不同的上界和下界。比如 $2n+1$ 既可以记作 $O(n)$，也可以记作 $O(n^2)$。

这种记法可以让我们更准确的把握程序所需的计算资源和数据规模 $n$ 之间的关系。

例题 CCF 1034 钞票兑换 · 枚举优化

我们以一道题目为例，题目链接：CCF 1034 钞票兑换。

题目大意：将任意给定的整百元钞票，兑换成10元、20元、50元小钞票形式。输出兑换方案总数。

数据范围：输入需要兑换的钞票总数 $n$， $100⩽n⩽1.7\times {10}^{11}$。

时间限制：400 毫秒。

思路 0

这道题显然是可以通过穷举（枚举）解决。简单起见，记兑换得到 $10$ 元 $a$ 张，$20$ 元 $b$ 张，$50$ 元 $c$ 张，并记 $n=100k$。

只需遍历所有的 $a,b,c$，分别测试 $10a+20b+50c=100k$ 即可。

#include <stdio.h>
typedef long long i64;

int main() {
  i64 n, sum = 0;
  scanf("%lld", &n);
  for (i64 c = 0; c <= n / 50; c++) {
    for (i64 b = 0; b <= n / 20; b++) {
      for (i64 a = 0; a <= n / 10; a++) {
        if (a * 10 + b * 20 + c * 50 == n)
          sum++;
      }
    }
  }
  printf("%lld", sum);
}

#include <stdio.h>
typedef long long i64;

int main() {
  i64 n, sum = 0;
  scanf("%lld", &n);
  for (i64 c = 0; c <= n / 50; c++) {
    for (i64 b = 0; b <= n / 20; b++) {
      for (i64 a = 0; a <= n / 10; a++) {
        if (a * 10 + b * 20 + c * 50 == n)
          sum++;
      }
    }
  }
  printf("%lld", sum);
}

三层循环一共需要枚举 $\frac{n}{50}\cdot \frac{n}{20}\cdot \frac{n}{20}=\frac{n^3}{{10}^4}$ 种情况。因此程序的复杂度为 $O(n^3)$。

由于枚举中进行检验的代码足够简单，我们简单的估算为每秒可以进行 ${10}^9$ 次枚举。

针对题目的四个样例，我们可以进行大概的估算：

数据规模	枚举次数	估算时间	实际测量
$n=100$	${10}^2$	100 纳秒	0 毫秒
$n=4\times {10}^4$	$6.4\times {10}^9$	6400 毫秒	3147 毫秒
$n=2\times {10}^6$	$8\times {10}^{14}$	222.2 小时	-
$n=2\times {10}^{10}$	$8\times {10}^{26}$	25367833587 年	-
$n=1.7\times {10}^{11}$	留做习题	-	-

这份代码预期需要运行 253 亿年才能得到答案，可见我们的算法效率有多糟糕了，怎么可能不超时呢？我们需要优化。

优化 1

注意到我们在枚举三个数字判断其和是否是 $n$。我们能否定下两个数字，解算出第三个数字？这样可以避免一层枚举。

注意到 $a=10k-5c-2b$，即当 $b,c$ 确定时可以计算出 $a$，判断是否 $a⩾0$ 即可。如此可以消掉一层循环。

#include <stdio.h>
typedef long long i64;

int main() {
  i64 n, sum = 0;
  scanf("%lld", &n);
  for (i64 c = 0; c <= n / 50; c++) {
    for (i64 b = 0; b <= n / 20; b++) {
      i64 a = n / 10 - 5 * c - 2 * b;
      if (a >= 0)
        sum++;
    }
  }
  printf("%lld", sum);
}

#include <stdio.h>
typedef long long i64;

int main() {
  i64 n, sum = 0;
  scanf("%lld", &n);
  for (i64 c = 0; c <= n / 50; c++) {
    for (i64 b = 0; b <= n / 20; b++) {
      i64 a = n / 10 - 5 * c - 2 * b;
      if (a >= 0)
        sum++;
    }
  }
  printf("%lld", sum);
}

两层循环一共需要 $\frac{n}{50}\cdot \frac{n}{20}=\frac{n^2}{{10}^3}$ 次枚举。因此程序的复杂度为 $O(n^2)$。

我们可以继续估算：

样例规模	枚举次数	估算时间	实际测量
$n=100$	$10$	10 纳秒	0 毫秒
$n=4\times {10}^4$	$1.6\times {10}^6$	1.6 毫秒	1 毫秒
$n=2\times {10}^6$	$4\times {10}^9$	4000 毫秒	2227 毫秒
$n=2\times {10}^{10}$	$4\times {10}^{17}$	4629 天	-
$n=1.7\times {10}^{11}$	留做习题	-	-

不错，我们成功的从 253 亿年优化到了 4629 天，起码能活着看到结果了。能不能再给力一点呢？

优化 2

对 $a⩾0$ 求解，得到 $b⩽5k-2.5c$。因此 $b$ 是 $[0,5k-2.5c]$ 之间的整数，即我们需要求和

$$\sum _{c=0}^{2k}\lfloor 5k-2.5c+1\rfloor$$

又消掉一层。

#include <stdio.h>
typedef long long i64;

int main() {
  i64 n, sum = 0;
  scanf("%lld", &n);
  for (i64 c = 0; c <= n / 50; c++) {
    sum += (n - 50 * c) / 20 + 1;
  }
  printf("%lld", sum);
}

#include <stdio.h>
typedef long long i64;

int main() {
  i64 n, sum = 0;
  scanf("%lld", &n);
  for (i64 c = 0; c <= n / 50; c++) {
    sum += (n - 50 * c) / 20 + 1;
  }
  printf("%lld", sum);
}

现在只需 $\frac{n}{50}$ 次枚举了。继续估算：

样例规模	枚举次数	估算时间	实际测量
$n=100$	$2$	2 纳秒	0 毫秒
$n=4\times {10}^4$	$800$	0.8 微秒	0 毫秒
$n=2\times {10}^6$	$4\times {10}^4$	40 微秒	0 毫秒
$n=2\times {10}^{10}$	$4\times {10}^8$	400 毫秒	290 毫秒
$n=1.7\times {10}^{11}$	$3.4\times {10}^9$	3400 毫秒	2134 毫秒

非常精彩的优化，从 4629 天优化到了 3.4 秒。但是很遗憾我们离最终目标 400 毫秒还有一定的距离。可以再给力一点吗？

优化 3

优化 2 中我们得到了一个求和式，其实可以使用一定的数学技巧对求和式直接化简。提出首项

$$\sum _{i=0}^{2k}\lfloor 5k-2.5i+1\rfloor =5k+2k+\sum _{i=1}^{2k}\lfloor 5k-2.5i\rfloor$$

分奇偶展开有

$$\begin{array}{rl}\sum _{i=1}^{2k}\lfloor 5k-2.5i\rfloor & =\sum _{i=1}^k\lfloor 5k-2.5(2i-1)\rfloor +\sum _{i=1}^k\lfloor 5k-2.5(2i)\rfloor \\ & =\sum _{i=1}^k(10k-10i+2)\\ & =5k^2-3k+1\end{array}$$

于是可以写出代码

#include <stdio.h>
typedef long long i64;

int main() {
  i64 n, sum = 0;
  scanf("%lld", &n);
  sum = (5 * k + 4) * k + 1;
  printf("%lld", sum);
}

#include <stdio.h>
typedef long long i64;

int main() {
  i64 n, sum = 0;
  scanf("%lld", &n);
  sum = (5 * k + 4) * k + 1;
  printf("%lld", sum);
}

此时枚举已经完全被我们优化掉了，无论怎样的数据范围都可以直接的计算出答案。

提示

直接抄是过不了题的，还有需要修正，观察一下数据范围。有时候拿不了全分，也要争取部分分。

习题

思考的深度不同，对应代码的效率差距天差地别。学会分析自己思路的复杂度，是一个必须掌握的技能。

• 求下面函数的复杂度。

int f(int n) {
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n / i; ++j) {
      sum += 1;
    }
  }
  return sum;
}

int f(int n) {
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n / i; ++j) {
      sum += 1;
    }
  }
  return sum;
}

• 求下面函数的复杂度。

int f(int n) {
  if (n <= 2)
    return 1;
  else
    return f(n - 1) + f(n - 2);
}

int f(int n) {
  if (n <= 2)
    return 1;
  else
    return f(n - 1) + f(n - 2);
}

参考阅读

• 复杂度 - OIWiki
• 计算理论基础 - OIWiki