复杂度

参考资料

衡量一个算法的快慢，一定要考虑数据规模的大小。所谓数据规模，一般指输入的数字个数、输入中给出的图的点数与边数等。一般来说，数据规模越大，算法的用时就越长。

而在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即 时间复杂度（Time Complexity）。

类似地，算法所使用的空间随输入规模变化的趋势可以用 空间复杂度（Space Complexity）来衡量。

渐近符号（Asymptotic Notation）是函数的阶的规范描述。

简单来说，渐近符号忽略了一个函数中增长较慢的部分以及各项的系数，而保留了可以用来表明该函数增长趋势的重要部分。

tip

根据换底公式，任何底数的对数增长率相同，只相差一个常数，因此在渐近复杂度中通常省略底数。

Example

计算时间复杂度：

for(int i=1;i<n;i++)
{
	for(int j=1;j<=n-i;j++)
	{
		// Θ(1)
	}
}

题解

时间复杂度为 $\Theta(n^2)$ 。

计算时间复杂度：

for(int i=1;i<=n;i++)
{
	for(int j=1;j<=n;j+=i)
	{
		// Θ(1)
	}
}

题解

时间复杂度为 $\Theta\left(\sum_{i=1}^{n}\left\lfloor\frac{n}{i} \right\rfloor\right)=\Theta(n\log n)$ 。（调和级数）

计算时间复杂度：

for(int i=1;i<=n;i++)
{
	for(int j=1;j<=n;j+=i)
	{
		for(int k=1;k<=n;k+=j)
		{
			// Θ(1)
		}
	}
}

题解

时间复杂度为 $\Theta(n^2)$ 。

主定理（Master Theorem）可以快速求得关于递归算法的复杂度。

假设有递归关系式：

T(n)=aT\left(\frac{n}{b}\right)+f(n)

其中 $n$ 为问题规模， $a$ 为递归的子问题数量， $\frac{n}{b}$ 为每个子问题的规模， $f(n)$ 为递归以外进行的计算工作。

则有：

T(n)= \begin{cases} \Theta(n^{\log_b a}) & f(n) = O(n^{\log_b (a)-\epsilon}),\epsilon > 0 \\ \Theta(f(n)) & f(n) = \Omega(n^{\log_b (a)+\epsilon}),\epsilon\ge 0 \\ \Theta(n^{\log_b a}\log^{k+1} n) & f(n)=\Theta(n^{\log_b a}\log^k n),k\ge 0 \end{cases}

Example

计算时间复杂度：

T(n)=2T\left(\frac{n}{2}\right)+\Theta(1)

题解

时间复杂度为 $\Theta(n)$ 。