时间复杂度计算-例题集合

一、常数阶

int result = 100; //运行程序只执行一次  
 
result ++ ;  //执行一次
 
System.out.println ("Hello!"+result); //执行一次 

上面算法的运行的次数的函数为f(n)=3，根据推导大O阶的规则1，每次运行程序每条语句执行一次，所以这个算法的时间复杂度仍旧是O(1)，我们可以称之为常数阶。
二、线性阶

 
for(int i=0;i<n;i++){
 
   System.out.println(result[i]);  //执行一次
 
}

线性阶主要要分析循环结构的运行情况。
上面算法循环体中的代码执行了n次，因此时间复杂度为O(n)，实际上，在for循环里面的所有时间复杂度为O(1)的语句总的时间复杂度都是O(n)。
三、对数阶

 
int result=1;
 
while(result<n){
 
    result=result*2; //时间复杂度为O(1)
 
}

可以看出上面的代码， result=result*2; 随着result每次乘以2后，都会越来越接近n，当result大于等于n时就会退出循环（限制条件）。
如果循环的次数为T，所以2^T=n于是T=log₂n，因此得出这个算法的时间复杂度为O(logn)。
四、平方阶

     
    for(int i=0;i<n;i++){       
       for(int j=0;j<n;i++){     
           System.out.println(result[i][j]);  //执行一次     
       }     
    }

这是一个循环嵌套的语句，很明显内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，又经过了外层循环n次，那么这段算法的时间复杂度则为O(n²)。