时间复杂度是什么,干嘛用？ – 源码巴士 |
您所在的位置：网站首页 › 10001什么意思 › 时间复杂度是什么,干嘛用？ – 源码巴士 |
时间复杂度是什么,干嘛用？ – 源码巴士
|
大家初学编程，做编程练习时,可能会遇到这种情况
自己在电脑上运行输入数据，能得到正确的结果，但是网站评测的结果却是0分，或者部分分数。 我们思考一下，影响程序解决问题速度的因素有哪些？ 第一个因素，问题规模。 比如同样判断质数，判断100以内的数字和一个数十亿的数字，计算量差别很大。 第二个因素，计算机性能。
同样的问题，普通电脑和超级计算机的运算时间差距，也是不可想象的。 第三，代码本身的效率。
对于一个公司来说，提升网站性能的方法主要是后两点，而且提升代码效率的代价远远低于提升服务器。 而在编程竞赛中，我们的代码在评测机上进行评测，那么数据范围和计算机的性能是固定的，那我们避免超时的唯一手段就是提升代码效率。 那么时间复杂度是什么呢？ 时间复杂度：衡量算法效率的指标，指出算法解决问题执行的计算工作量和问题规模的关系。 一般取最差情况时间复杂度。 我们可以把 o ()理解成大约的意思。 把计算量算出来，取其中最大的一项作为时间复杂度。 比如以下代码。 #include using namespace std; int main() { int l,a[10001]={0},m,u,v,s=0; cin>>l>>m; for(int i=0;i>u>>v; for(int j=v;j>=u;j--) { a[j]=1; } } for(int i=0;i 各种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)，最大公约数相信通过这篇文章，大家对时间复杂度这个概念会有更深入的理解，有问题的话欢迎评论或私信。 |
【本文地址】