关于时间:
评测系统呈现的是运行时间,一般说来时间测量都不是特别准确的,都会有小的误差,但是误差波动不大,不会有数量级的波动。影响代码实际运行效率的因素比较宏观当然是看理论的平均复杂度,做优化算法基本也是优化这个,但是还有很多微观一点的细节:
1、某些算法的极限情况会造成复杂度最差(比如快排)。
2、算法实际的常数很大,在一些极限一点的情况渐近复杂度不能显示出效率的差距,效率差距主要体现在常数上。
3、使用了一些可能常用的库函数,建议去弄清这些东西的复杂度。
比如std:sort 这个排序跑得飞快。。。
比如std::nth_element 可以认为是O(n)的。。然后在元素个数小于等于3的时候用的插排。。
有时候因为对库函数的复杂度不清楚,随意用上去会算不清具体的复杂度。
4、语言差异造成的IO差距和运行差距。比如在10^5
10^6这种输入量级的数据上可以对比下scanf和cin的效率差距,其他语言也可以做做对比。另外有些语言跑起来就是要慢一些。。。。
5、还有一些丧心病狂的优化技巧。。。。。。
关于空间:
空间测量基本是稳定准确的。一般算法题对空间是不做限制的,所以关于空间可能产生的问题就是爆栈空间,系统提供的栈空间是有限的,在一个局部开一个很大的数组是有爆栈风险的。这个空间大小主要看评测机是啥操作系统的,一般都是linux。
综上。。。个人认为对于能通过的题目可以不太需要care使用的时间空间,需要比较关注的是这个问题的理论最优复杂度算法的写法。。以及一些很优雅的写法?