一、时间复杂度

T(n)=n+1 忽略常数项 T(n)~n

T(n)=n+n^2 忽略低阶项 T(n)~n^2

T(n)=3n 忽略最高阶的系数 T(n)~n

常用的时间复杂度从小到大依次为：

O(1)  <  O(logn)  <  (n)  <  O(nlogn)  <  O(n^2)  <  O(n^3)   <  O(2^n)  <  O(n!)  <O(n^n)

（一）常数阶——O(1)

   以下算法的时间复杂度为（ o(1) ）。         

 int n=100;

     n=n+1;

      system.out.println(n);

    解析：  该语句执行一次，所以时间复杂度为o(1) 。

 （二）线性阶——O(n)

    以下算法的时间复杂度为(  o(n) ) 。

public static void main(string[] args){

    int n=100;

     for (int i=0;i<n;i++){

        system.out.println("text");
        }
    }

解析： n=100,i=0,i<n,text,i++

            n=100,i=0,0<100,text,i=1

            n=100,i=1,1<100,text,i=2

            n=100,i=2,2<100,text,i=3

            .............

            n=100,i=99,99<100,text,i=100

该语句段一共执行100次，执行次数由n决定，所以该语句的时间复杂度为o(n)。

（三）平方阶——O(n^m)

   1、以下算法的时间复杂度为(  o(n^2) ) 。

​int x=1;
int i=1;
  for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

​

解析：相当于把o(n)的代码再循环嵌套了一次，所以时间复杂度就是o(n*n)=o(n^2)。

   2、以下算法的时间复杂度为( o(mn) ) 。

int i=0;
int j=0;
for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        a[i] [j]=0;

解析：a[ i ][ j ]=0是基本语句，该代码内循环执行了m次，外循环执行了n次，所以一共执行了m*n次，时间复杂度就是o(mn)。

（四）对数阶——O(log n)

    以下算法的时间复杂度为( O(log2n) ) 。

int i=1;
while(i<=n)
    i=i*2;

解析：n=5,i=1,i<5,i=1*2=2

                  i=2,i<5,i=2*2=4

................

每次i=i*2之后，i离n的距离就越来越近，当循环m次后，i>n时，循环就结束了

所以 2m=n——m=log2n，所以时间复杂度就是o(log2n)。