一、常见的

1.线性的

T（n） = 3n，执行次数是线性的。

public void eat(int n){
    for(int i=0; i<n; i++){;
        System.out.println("等待一天");
        System.out.println("等待一天");
        System.out.println("吃一寸面包");
    }
}

2.对数的

T（n） =，执行次数是对数的。

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

变形 T（n） =，执行次数是对数的。

int i=1;
while(i<n){
    i=i*3;
}

T（n） = ，执行次数是对数的。(这种的 2省略掉了)

public void eat2(int n){
   for(int i=1; i<n; i*=2){
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("吃一半面包");
   }
}

线性对数阶O(nlogN)

将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，

for(int m=1;m<n;m++){
    int i=1;
    while(i<n){
        i=i*2;
    }
}

3.常量的

T（n） = 2，执行次数是常量的。

public void eat3(int n){
   System.out.println("等待一天");
   System.out.println("吃一个鸡腿");
}

4.多项式

T（n） = 0.5n^2 + 0.5n，执行次数是一个多项式。
(1+2+3+……+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。)

public void eat4(int n){
   for(int i=0; i<n; i++){
       for(int j=0; j<i; j++){
           System.out.println("等待一天");
       }
       System.out.println("吃一寸面包");
   }
}

平方阶

它的时间复杂度就是 O(n²)。

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

二、渐进时间复杂线

如何推导出时间复杂度呢？有如下几个原则：

1. 如果运行时间是常数量级，用常数1表示；
2. 只保留时间函数中的最高阶项；
3. 如果最高阶项存在，则省去最高阶项前面的系数。

一、线性的
T（n） = 3n
最高阶项为3n，省去系数3，转化的时间复杂度为：
T（n） = O（n）

二、对数的
T（n） = 5logn
最高阶项为5logn，省去系数5，转化的时间复杂度为：
T（n） = O（logn）

3.常量的
T（n） = 2
只有常数量级，转化的时间复杂度为：
T（n） = O（1）

4.多项式
T（n） = 0.5n^2 + 0.5n
最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：
T（n） = O（n^2）

总结：
这四种时间复杂度究竟谁用时更长，谁节省时间呢？稍微思考一下就可以得出结论：
O（1）< O（logn）< O（n）< O（n^2）