C++-时间复杂度

前言

        OJ测试中最烦人的结果莫过于TLE(Time Limit Exceed 超时)和MLE(Mempry Limit Exceed超内存）了，在递归和搜索题里面看见这两货就烦。

目录

前言

时间复杂度 

        时间复杂度概念

时间复杂度的表示法

        时间复杂度OJ测试要求

         时间复杂度例举

时间复杂度 

        时间复杂度概念

        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)