蓝桥杯入门

恭喜你,现在大致了解了蓝桥杯竞赛的一些常见题型和有关注意事项。
接下来是一些有关算法性能判定的介绍。

时间复杂度和空间复杂度

算法的复杂度是评估算法性能优劣的一个重要指标,可以帮助信息学竞赛选手估算出算法在执行之后所需要的时间和空间,所以分析算法的复杂度几乎成了每个选手必须掌握的能力。

算法的复杂度分为算法的时间复杂度和空间复杂度。在介绍时间复杂度之前,我们需要先了解什么是 时间频度

一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。

请问时间频度和时间复杂度是一个概念吗? – V2EX

时间频度是算法中语句的执行次数,用 $T(n)$ 来表示,$n$ 为问题的规模。

有时候,时间频度的表达方法有点复杂,我们需要更直观的表达方法,于是引入了时间复杂度的概念。如果有一个辅助函数 $f(n)$,在 $n$ 趋向于无穷大时,$T(n)/f(n)$ 的极限值为不等于 $0$ 的常数,则我们近似的将 $f(n)$ 替代 $T(n)$,记为 $T(n)=Ο(f(n))$,称为算法的渐进时间复杂度。

时间复杂度只关心算法中最耗时的部分,舍去常数部分,通常用简单的函数来表示。例如,某算法计算出来 $T(n)=2n^{3}+4n^{2}+n$,则它的时间复杂度为 $O(n^{3})$。按效率从高到低排列,时间复杂度一般有以下几种:

常数阶对数阶线性阶线性对数阶平方阶立方阶指数阶阶乘阶
$O(1)$$O(\log n)$$O(n)$$O(n\log n
)$
$O(n^{2})$$O(n^{3})$$O(2^{n})$$O(n!)$

为了方便理解,这里举一个算法时间复杂度计算过程的例子:
现有如下代码,可以计算出语句 1 执行了 $n^{2}$ 次,语句 2 执行了 $n$ 次,语句 3 执行了 $\log n$ 次,则 $T(n)=n^{2}+n+\log n$,取其中最耗时的部分,并用熟悉的函数表示,则时间复杂度为 $O(n^{2})$。

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

for(int i = 0; i < n; i++){
	b++;	// 2
}

while(n){
	n = n / 2;	//3
}

算法的空间复杂度是指运行该算法所占用的存储空间大小,记为 $S(n)$,和时间复杂度类似,通常也是取它的渐进空间复杂度,用一个直观的函数来表示。通过空间复杂度,我们可以预估出算法运行所需的存储空间,包括指令空间、数据空间、动态申请的内存空间等。

有如下代码,可以计算出 $S(n)=n+n^{2}$,则空间复杂度为 $O(n^{2})$。

int a[n];
int b[n][n];

在竞赛中,我们认为计算机一秒能执行 $5*10^{8}$ 计算。
如果题目给出的限时为 1 秒,那么你选择的算法执行的计算次数最多应当限制于 $10^{8}$ 量级内才不至于 TLE。

  • $O(n)$ 的算法能解决的数据范围在 $n\leqslant 10^{8}$。
  • $O(n\log n)$ 的算法能解决的数据范围在 $n\leqslant 10^{6}$。
  • $O(n\sqrt{n})$ 的算法能解决的数据范围在 $n\leqslant 10^{5}$。
  • $O(n^{2})$ 的算法能解决的数据范围在 $n\leqslant 5000$。
  • $O(n^{3})$ 的算法能解决的数据范围在 $n\leqslant 300$。
  • $O(2^{n})$ 的算法能解决的数据范围在 $n\leqslant 25$。
  • $O(n!)$ 的算法能解决的数据范围在 $n\leqslant 11$。

以上仅供参考,因为整个程序往往还有其它内容需要耗时,例如算法中的常数。

页面: 1 2

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注