关于刷题入门(时间和空间复杂度)的总结


时间和空间复杂度

在刷题过程中会遇到一些超时的现象,这就说明你的算法不符合题目要求的运行时间,称为超时。

时间复杂度:目前通俗来讲就是程序在完成后台测试数据(每组数据对应一个时间,所有时间都符合才可以)要花的时间,如果这个时间超过题目要求的时间(通常是1000ms)就会超时。它的具体定义以及公式计算等等会在数据结构这本书上出现。

空间复杂度:通俗来讲就是程序所占的内存。刷题中,这种情况很少出现这个超出限制。

Time Limited Exceed(超时)

简称TLE。通常需要进行算法优化来降低时间复杂度,加快代码运行的时间。 
常见的TLE有以下几种情况:

1、程序中出现无法终止的死循环
2、读取输入流和输出流的时间太长。(C++的输入输出中,cin和cout没有scanf和printf快,不要问我是怎么知道的,我都已经在输入输出上载过无数跟头了….建议同学们养成用scanf和printf的好习惯)
3、时间复杂度大,常常是多层循环或者深递归导致。建议大家能不用循环的时候,就不用循环,因为循环费时。

如何判断自己的程序是否会超时:  首先看题目数据的大小, 会给一个数据范围,比如0<N <1000, 接下来看你的程序的代码的语句一共运行多少次, 基本上就是看 循环的层数(一般是看有多少个for嵌套或者while)。N为上面那个范围,要考虑极限数据 就是 N = 1000的情况, 三个for嵌套 就是 1000的三次方 等于10亿 对于这个数量级程序就会超时。 程序执行语句次数一般控制在10^7 到10^8以下 就不会超时,这个是因为计算机每秒可以运行大概10^8条语句。


文章作者: Cone
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 Cone !
  目录