首先：

  常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log₂n)＜Ο(n)＜Ο(nlog₂n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)＜Ο(n!)

时间复杂度可以简单理解为最多执行次数。

一、O(1)

一般情况下没有其他循环和递归调用，时间复杂度一般都是O(1)。比如下面这样的代码

#include<iostream>
using namespace std;
int main(){
	int a=0,b=0,x=0,y=0;
	cin>>a>>b;
	x=a+b;
	y=a-b;
	if(x>y){
	 cout<<x;
	}else{
	 cout<<y;
	}
	return 0;
}

二、O(n)

一般情况下，一个循环的时间复杂度是O(n)，多个循环并列也是取循环次数最多的那个作为时间复杂度。当数据量增大n倍，耗时增大n倍。

#include<iostream>
using namespace std;
int main(){
	int a=n;
	cin>>n;
	for(int i=0;i<n;i++){
	    cout<<i;
	}
	return 0;
}

三、O(n²)、O(n*m)

双重循环嵌套一般就是O(n²)。当数据量增大n倍，耗时增大n方倍。

#include<iostream>
using namespace std;
int main(){
	int n=0;
	cin>>n;
	for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	        cout<<i;
	    }
	}
	return 0;
}

如果循环嵌套外层循环是n，内层循环是m。

#include<iostream>
using namespace std;
int main(){
	int n=0,m=0;
	cin>>n>>m;
	for(int i=0;i<n;i++){
	    for(int j=0;j<m;j++){
	        cout<<i;
	    }
	}
	return 0;
}

这个时候的时间复杂度是O(n*m)。

四、O(logn)

当数据增大n倍时，耗时增大logn倍。

#include<iostream>
using namespace std;
int main(){
	int n=0;
	cin>>n;
	for(int i=0;i<n;i++){
	   i*=2;
	   cout<<i;
	}
	return 0;
}

本来循环次数是n，现在i*=2了。那么答案是log(2)(n)。

反着想也可以，原来循环n次，现在每次i变成原来的2倍，也就是2的k次方等于n。那么正好就是log(2)(n)，即O(log n)

或者下面这样：

#include<iostream>using namespace std;
int main(){
int n=0;
cin>>n;
while((n=n/2)>0){
    cout<<n;
}
 return 0;
}

时间复杂度也是O(logn)

五、O(nlogn)

一般归并排序和堆排序是O(nlogn)。 

常见的是外层循环的时间复杂度是n，内层循环的时间复杂度是logn。

比如下面这样：

for(int i=1; i<=n; i++)
{
	for(int j=1; j<=n; j+=i)
	{
		.....   //复杂度为O(1);
	}
}

注意：外层循环是n，内层循环j每次都增加i。

常见算法的时间复杂度