Question

请问在noip和noi这种信息学竞赛中，程序的时间复杂度在10的几次方内不会超时（1s）？

我听了好几个版本了，求正解！

Answer 1

一般是10^8左右，但是还要看常数，比如说for循环1亿次基本不会超。但是1亿次除法就很危险了。
LS说的比较全了。但是O(n^3)，500很危险，除非Floyd等常熟特别小的。O(nlogn)的话，线段树平衡树等都只能到10w，如果是动态树什么的只能四五万，堆的话可以20w左右，排序1000000个数基本上到顶了。
此外数组大小和寻址方式也会制约程序时间，比如。
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j) a[i][j];
和
for (int j=1;j<=n;++j)
for (int i=1;i<=n;++i) a[i][j]
差距很大

Answer 2

首先还是要看语言的吧 一般来说C/C++要比pascal快一些

我用C多一点 我个人的经验是运算次数上限大概在七八千万左右，这个值要根据评测环境浮动，一般来说在比赛时，我要卡时的时候会把时间控制在0.8s左右（我觉得基本上不会出现什么考试的机器比评测的机器差了好几个档次的吧///）

排序的话100W是极限（基本上必TLE,祈祷评测环境好一点的吧）

N^3 的500基本上也到极限了

线段树的话要看写法。。。。比如zkw线段树的常数就要比自顶向下递归的线段树小很多，而且也是要看题决定的。。。有些题线段树50W也能在1s中处理完

平衡树看种类了 treap和sbt都比较快 Splay稍慢但用处更大 （我相信NOI/NOIp中没有人用红黑树和AVL树吧） 基本上也是10W，20W的样子

二叉堆的话好像50W没问题，常数比较小

动态树什么的一般是Splay+Splay.....Splay的常数比较大。。。所以也就是四五万

其他制约时间的方面就基本上就是读入和储存之类的 因为寻找地址的关系。。。所以一维数组的操作比二维数组的操作快(dp中滚动数组优化时间的原理） 还有就是像楼上所写的i,j循环的顺序导致的时间差异（这是计算机自身储存方式决定的）

顺便说一下如果还要优化的话就是读入 比如fread > scanf > cin fread基本上是各神犇在OJ上优化程序时间效率的常用手段

还有一个就是函数的内联优化 就是说调用函数是要耗时间的 而采用函数的内容替代调用函数可以优化时间 （实际中可以用g++ 的 -o2编译）

Answer 3

运行次数1-2亿 再多就会爆
O(N2) 8000左右
O(N3) 500左右
O(N LOG N）一般500000左右 排序能2000000
悬赏这么多分 抢的人肯定多饿 都不敢上线回答了（采纳率~）

Answer 4

9 一般的评测机器是一亿次