时间复杂度

• 时间复杂度是衡量算法好坏的一个重要指标。
• 衡量代码的好坏，包括两个非常重要的指标：运行时间和占用空间

如果代码没有运行起来，怎么预知代码运行所花的时间呢？
代码的绝对时间是无法估计的，但我们却可以预估出来代码的基本操作执行次数。

---

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

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

最高阶项为3n，省去系数3，转化的时间复杂度为：

T（n） = O（n）

---

场景2：T（n） = 5logn，执行次数是对数的。

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("吃一半面包");
   }
}

最高阶项为5logn，省去系数5，转化的时间复杂度为：

T（n） = O（logn）

---

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

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

只有常数量级，转化的时间复杂度为：

T（n） = O（1）

---

场景4：T（n） = 0.5n^2 + 0.5n，执行次数是一个多项式。

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

最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：

T（n） = O（n^2）

---

时间复杂度按n越大算法越复杂来排的话：常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n²)、立方阶O(n³)、……k次方阶O(n的k次方)、指数阶O(2的n次方)。

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