时间复杂度是什么,干嘛用？

大家初学编程，做编程练习时,可能会遇到这种情况

自己在电脑上运行输入数据，能得到正确的结果，但是网站评测的结果却是0分，或者部分分数。

我们思考一下，影响程序解决问题速度的因素有哪些？

第一个因素，问题规模。

比如同样判断质数，判断100以内的数字和一个数十亿的数字，计算量差别很大。

第二个因素，计算机性能。

同样的问题，普通电脑和超级计算机的运算时间差距，也是不可想象的。

第三，代码本身的效率。

对于一个公司来说，提升网站性能的方法主要是后两点，而且提升代码效率的代价远远低于提升服务器。

而在编程竞赛中，我们的代码在评测机上进行评测，那么数据范围和计算机的性能是固定的，那我们避免超时的唯一手段就是提升代码效率。

那么时间复杂度是什么呢？

时间复杂度：衡量算法效率的指标，指出算法解决问题执行的计算工作量和问题规模的关系。

一般取最差情况时间复杂度。

我们可以把 o ()理解成大约的意思。

把计算量算出来，取其中最大的一项作为时间复杂度。

比如以下代码。

#include<iostream>
using namespace std;
int main()
{
	int l,a[10001]={0},m,u,v,s=0;
	cin>>l>>m;
	for(int i=0;i<m;i++)
	{
		cin>>u>>v;
		for(int j=v;j>=u;j--)
		{
			a[j]=1;
		}
	}
	for(int i=0;i<=l;i++)
	{
		if(a[i]==1)
		s++;
	}
	cout<<l-s+1<<endl;
	return 0;
}

总的计算量是 m*(u-v)+l.

结合数据范围看，时间复杂度是o（m*l），注意这里是按最极端的情况算。

然后时间复杂度结合数据范围，计算可得，运算量为 100 * 10000 即100万。

而我们 c++ 程序在评测机上 1S 的运算量 范围在 10⁷ - 10⁸ .

一般情况下，时间限制是1S或者2S。

那么 我们可以的出结论，上面的代码不会超时。

常见的时间复杂度

o（1） 无论什么数据范围，都是进行固定的几次运算。

o (log n) 比如二分查找，就是这个复杂度。

o（√ n）

o（n）

o (n²)

o (n³)

等等。

各种规模数据可选的算法时间复杂度

这里的时间是按照每秒5000万运算计算的，实际时间可能会有轻微波动。

同样的题目，数据范围不同时，采用的算法可能完全不同。

所以，在做编程练习时，我们甚至应该在读题目之前先看数据范围，这样的话 ，我们就能排除一些算法，甚至在读题之前就对题目应该采用哪种算法胸有成竹！！！

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

n≤30n≤30, 指数级别, dfs+剪枝，状态压缩dp
n≤100n≤100 => O(n3)，floyd，dp
n≤1000n≤1000 => O(n2)，O(n2logn)，dp，二分
n≤10000n≤10000 => O(n∗n√)O(n∗n)，块状链表
n≤100000n≤100000 => O(nlogn)=> 各种sort，线段树、树状数组、set/map、heap、dijkstra+heap、spfa、求凸包、求半平面交、二分
n≤1000000n≤1000000 => O(n) 以及常数较小的 O(nlogn) 算法 => hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn)) 的做法：sort、树状数组、heap、dijkstra、spfa
n≤10000000n≤10000000 => O(n)，双指针扫描、kmp、AC自动机、线性筛素数
n≤109n≤109 => O(n√)O(n)，判断质数
n≤1018n≤1018 => O(logn)，最大公约数

相信通过这篇文章，大家对时间复杂度这个概念会有更深入的理解，有问题的话欢迎评论或私信。