如何估算时间复杂度
首先：
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(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(n2)、O(n*m)
双重循环嵌套一般就是O(n2)。当数据量增大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。