复杂度

参考资料

衡量一个算法的快慢，一定要考虑数据规模的大小。

所谓数据规模，一般指输入的数字个数、输入中给出的图的点数与边数等等。一般来说，数据规模越大，算法的用时就越长。

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

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

提示

由换底公式可以得知，任何对数函数无论底数为何，都具有相同的增长率，因此渐进时间复杂度中对数的底数一般省略不写。

示例

for(int i=1;i<n;i++)
{
	for(int j=1;j<=n-i;j++)
	{
		if(a[j]>a[j+1])swap(a[j],a[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}

示例

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

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