如何评价算法优劣

算法是一个能够解决问题的确切方法。因此，算法是否正确是评价一个算法优劣很重要的方法。但是评价算法优劣不止这一种方法，好的算法还需要运行速度快，占用内存小等特性，这在算法竞赛中变得极为重要。

因超时而TLE的测试点

题目往往会有时间和空间限制

”时间一去不复返“，这句话也适用于算法竞赛，显然时间限制是每个oier（算法竞赛者）应该第一考虑的问题，而空间限制往往较为宽松，有时则完全不需要考虑。

注意：题目中未标出时间空间限制的，并不意味着没有，只是隐藏起来了，用来迷惑做题者

时间复杂度

我们不能确切计算出每种算法的运行时间，但是我们可以粗略比较不同算法之间的效率差异。这就需要用到基础操作执行次数。每次执行基本操作花费的时间可以看作是相同的。所以基础操作执行次数的多少决定了算法效率的高低。这通常用大O来表示。没有特殊说明大O表示的是最坏时间复杂度。

假使有以下代码，用来计算1~n的累加和：

#include<iostream>using namespace std;int main(){	int n,sum=0;	cin>>n;	for(int i=1;i<=n;i++){		sum+=i;	}	cout<<sum;	return 0;}

可以看到：这段代码一共有n+3（循环的判断，自增暂不计）次基础操作。于是它的时间复杂度是O(n+3)。但是我们在日常做题时往往有很长很复杂的代码，这样时间复杂度就可能是这样：O()或这样O()，这样时间复杂度就很难比较出孰优孰劣。因此我们需要化简时间复杂度。

化简时间复杂度有以下两个原则：

只保留最高次数项。去除常数项和系数。

这样O( )就变为O( )，O( )就变为O( )。

于是，所有时间复杂度都可以化为一下几类。(其中O(1)的意思是算法执行的基础操作与问题规模无关）

O(1)、O(logn)、O(n)、O(nlogn)、O( n^2 )、O( n^k )k为常数、O( 2^n )、O(n!)。

各时间复杂度图像

如图所示：O(1)<O(logn)<O(n)<O(nlogn)<O( n^2 )<O( n^k )<O( 2^n )<O(n!)

各时间复杂度详解

O(1)

算法的时间消耗与问题规模无关，例如定义变量、访问数组都是O(1)时间。

int a[101][101];int c=a[2][2];

O(logn)

基本和O(1)时间无异，这个时间非常高效，是所有算法可能达到的最优时间复杂度，例如二分法。

O(n)

最普通的时间复杂度，例如遍历数组。

O(nlogn)

这个时间复杂度还不错，是一般算法能达到的最优时间复杂度，例如快速排序。

O(n^2)

这个时间复杂度能用，但不是非常高效，例如冒泡排序。

O(2^n)

这个时间复杂度一般是子集问题，因为子集有2^n个。

O(n!)

这个时间复杂度一般是全排列问题，因为全排列有n!个。

各时间复杂度可用度

保险来算现代计算机的指令处理速度大约是每秒千万次级。据此制作下表：

问题规模n

O(logn)

O(n)

O(nlogn)

O(n^2)

O(2^n)

O(n!)

n<11

√

√

√

√

√

√

n<25

√

√

√

√

√

×

n<5000

√

√

√

√

×

×

n<1000000

√

√

√

×

×

×

n<10000000

√

√

×

×

×

×

n>100000000

√

×

×

×

×

×

此表无需死记硬背，了解即可。