OI（信息学竞赛）常用术语解析

2023-11-01 16:08| 来源: 网络整理| 查看: 265

一测试点状态

二时间复杂度

三空间复杂度

一测试点状态简称全称意思图片ACAccepted该测试点答案正确无误

WAWrong Answer该测试点答案错误

TLETime Limit Exceeded该测试点运行时间超出限制（重点排查死循环，改进算法，降低时间复杂度）

MLEMemory Limit Exceeded该测试点占用内存超出限制（很少发生，重点排查数组定义过大）

OLEOutput Limit Exceeded输出超出限制（通俗点讲，就是输出太多东西了）

UKE

Unknown Error该测试点发生未知错误

之前编辑时缺了一个RE，下面补上

RERuntime Error该测试点发生运行时错误（重点排查数组过小，也有可能是除以0，对0取余，以及main()返回值不为0）

二时间复杂度

各题的题解中经常看到有人说某种解法的时间复杂度为 $O(log n)$ 、 $O(n^2)$ 等，那么究竟什么是时间复杂度呢？

先来看一个具体的例子，有一段C++代码如下：

#include using namespace std; int main(){ int a,b; cin>>a; for(int i=0;ib; } } return 0; }

其中，return 0这句不计入时间复杂度的计算；

不管变量名是什么，时间复杂度的多项式表达总用n来表示，因此：

对于cin>>a，i=0，j=0，只需做一次，总时间复杂度为 $O(3)$ ；

对于内层for循环，j>b也要进行这么多次，总复杂度为 $O(3n^2)$ ；

对于外层for循环，i

【本文地址】

今日新闻