前言
OJ测试中最烦人的结果莫过于TLE(Time Limit Exceed 超时)和MLE(Mempry Limit Exceed超内存)了,在递归和搜索题里面看见这两货就烦。
目录
时间复杂度
时间复杂度概念
C++时间复杂度是指算法在处理数据时所需要的计算时间。在C++中,常见的时间复杂度包括常数级别、对数级别、线性级别、平方级别、立方级别等。其中,常数级别是最快的,而立方级别是最慢的。具体来说:
常数级别:只需要一次计算即可完成,如赋值操作等。
对数级别:需要不断缩小问题规模,通常用于二分查找等算法。
线性级别:随着问题规模增加,所需计算时间也呈线性增长,如遍历一个数组等。
平方级别:通常是嵌套循环的形式,所需计算时间随着问题规模的增加呈平方级别增长。
立方级别:通常是三层嵌套循环的形式,所需计算时间随着问题规模的增加呈立方级别增长。
当然,在实际应用中,我们需要选择合适的算法来降低时间复杂度。例如,可以使用哈希表来加速查找操作,或者使用动态规划来减少重复计算等。在竞赛中,一般算机一秒能执行x
次汁算。
时间复杂度的表示法
对于表示时间复杂度,我们可以使用O()表示法来表示时间复杂度,O(n)表示程序运行n次汁算。判断时,只关注最高次项。但执行的数量不是不确定的都填1
比如下面的例子:
O(c) = O(1) (c表示常数)
O(2n+1) = O(n)
O(n²+n+1) = O(n²)
O(3n³+1) = O(n³)
注意:符号 O(c)表示算法或函数具有恒定的时间复杂度,这意味着无论输入大小如何,它都需要固定的时间来执行。
时间复杂度OJ测试要求
为了避免TLE,OJ中要减少时间复杂度,一般来讲(1000ms) n的数据范围大致如下
时间复杂度 | n算法数据范围 |
| |
| |
| |
| |
| |
| |
时间复杂度例举
O(1) 一般的输入输出,变量的定义 ,时间复杂度都为O(1)
printf("Hello,Wold");
int a=3,b=20;
return 0; //时间复杂度为O(1)
O(n) 一般的循环 ,时间复杂度都为O(n)
O(n^2) 一般的二重循环 ,时间复杂度都为O(n^2)
int n=123456;
for(int i=0;i<=n;i++){
for(int j=0;j<=i;j++)
cout<<"# ";
cout<<endl;
}
return 0; //时间复杂度为O(n^2)
O(n^3) 一般的三重循环 ,时间复杂度都为O(n^3)
O(2^n) 指数阶,如递归实现的斐波那契数列 ,时间复杂度都为O(2^n)
O(log n) 对数阶,如二分查找 ,时间复杂度都为O(log n)
O(n log n) 线性对数阶,例如快速排序,时间复杂度都为O(log n)
标签:OJ,复杂度,C++,算法,时间,级别,log From: https://blog.csdn.net/March_14th/article/details/140262359