复杂度理论初步

在算法竞赛中，我们不但要保证输出结果的正确性，还要在规定的时间内完成计算，才能够拿到该测试点的分数。一个问题可能有很多种算法来解决，但耗时有显著差异。冒泡排序一个长度为 $100000$ 的数组，耗时几分钟；快速排序耗时不到一秒钟。而衡量时间的多少，我们不一定非要逐个跑程序。在设计代码之前，我们往往可以估测耗时，这就需要用到复杂度理论。

$\log$ 问题

$\log$ （对数）是对指数的逆运算。说人话：

$\log_ab$ 是询问“$a$ 的多少次方等于 $b$”。

例子 $log_21024=10$，因为 $2$ 的 $10$ 次方是 $1024$。

特殊地

1. $\lg$：$10$ 为底的对数，叫作常用对数。
2. $\ln$：以无理数 $e$（$e=2.71828\cdots$）为底的对数，叫作自然对数。

运用对数可以解决很多问题，对于学习复杂度理论也很有帮助。

大 $O$ 记号

看看下面的代码，他将会执行多少次操作？

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

第 $5$ 行的 for 每次执行需要 $n$ 次操作；这个 for 一共被执行 $n$ 遍。即
$$n+n+\cdots+n=n^2$$
所以这个算法的时间复杂度为 $O(n^2)$

这个例子呢？

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

$$1+2+\cdots+n=\frac{n(n+1)}{2}=\frac{n^2+n}{2}=\frac{1}{2}n^2+\frac{1}{2}n$$

怎么判断这个算法的时间复杂度呢？

$n$ 很大的时候，$n^2$ 与 $\frac{n(n+1)}{2}$ 区别不太大。$O$ 记号表达的复杂度，是“最坏情况下，程序执行操作的总次数”。要注意的是：

• 如果是多个项相加，只取最大的项（最高次项）。
• 省略掉所有的常数。一般情况下包括系数和常数项。

例子

• $\frac{n(n+1)}{2}$ 是 $O(n^2)$ 的。
• $3n-10$ 是 $O(n)$ 的。
• $n^2+n+1$ 是 O(n2) 的。
• $233$ 是 $O(1)$ 的。

可见，$O$ 记号为我们提供了一种非常简便的方式来衡量复杂程度。再来几个例子：

• $233n^9-1000000n+1$ 是 $O(n^9)$。
• $1 + 2 + 4 + 8 +\cdots+ 2n$ 是 $O(2^n)$
• $123\log2(n) + 566\ln(n) + 10\lg(n)$ 是 $O(\log n)$

讲了太多形而上的东西，让我们把所学运用到代码中去吧！让我们再看一个例子。

int getSum(int n)
{
	sum = 0;
	for(i=1; i<=n; i++)
		for(j=n; j<=n+5; j++)
			sum += i*j;
	return sum;
}

注意到 $5-6$ 行的复杂度是 $O(1)$，一共执行 $n$ 次，所以是 $O(n)$。

问 calc 函数的时间复杂度。

void play()
{
	for(i=1; i<=n; i++)
		printf("Hello, World!");
}

void calc()
{
	for(int i=1; i<=n; i++)
		play();
}

play 函数复杂度是 $O(n)$，一共被调用 $n$ 次，所以总复杂度是 $O(n^2)$。

最后一个例子：

void play1() ... // 复杂度是 O(1) 的
void play2() ... // 复杂度是 O(n^2) 的
void play3() ... // 复杂度是 O(n) 的

void calc()
{
	for (int i=1; i<=n; i++)
	{
		play1();
		play2();
		play3();
	}
} 

$9-11$ 行的复杂度是 $O(n^2)$，一共被执行 $n$ 次，即
$$n(1+n^2+n)=n+n^3+n^2$$
复杂度是 $O(n^3)$ 的。

总结

• 我们以 $O$ 记号来表示程序的复杂程度。
• 时间复杂度是操作次数，空间复杂度是使用的内存大小。
• 复杂度只考虑数量级，例如 $2n + 233n^2$ 是 $O(2^n)$.
• 时间复杂度越大，程序跑的时间就越长。

关于程序运行时间：

• 可以估计，电脑一秒之内执行 $1$ 亿次运算。
• 根据经验，如果时间复杂度算出来在 $2\times10^7$（不用数了，这个数等于两千万） 以下，一般可以认为 $1s$ 之内能跑出来。