时间复杂度学习(上)

2018年10月9日

1，定义

时间复杂度一般采用大O标记法, 即 , 其中T(n)表示代码运行时间；n表示数据规模大小；f(n)表示每行代码执行次数总和， 表示T(n)与f(n)的正比关系。大 时间复杂度实际上并不具体表示代码的真正运行时间，而是表示代码执行时间随数据规模增长的变化趋势。

在大 表示分析中，低阶项和常数项都可以省略，只保留最高阶项即可；如 在大 标记法中记为 ，而对于形如 表示为 。

2，时间复杂度分析

• 关注循环次数多的代码

  public int accumulate(int n) {
      int sum = 0;
      int i = 1;
      for (; i <= n; i++) {
          sum += i;
      }
      return sum;
  }
  

  其中for循环内的代码执行n次，而其余代码执行1次，与n的大小无关，忽略常数项，该段代码的时间复杂度为 。

• 加法法则

  总复杂度为量级最大的那段代码的复杂度，抽象为公式为：

  若 ，，
  那么
  
  

  public int accumulate(int n) {
     int sum1 = 0;
     for (int i = 1; i <= 100; i++) {
         sum1 += i;
     }
  
     int sum2 = 0;
     for (int i = 1; i <= n; i++) {
         sum2 += i;
     }
  
     int sum3 = 0;
     for (int i = 1; i <= n; i++) {
         for (int j = 1; j <= n; j++) {
             sum3 += i * j;
         }
     }
     return sum1 + sum2 + sum3;
  }
  

  其中sum1段的代码循环执行了100次，与n无关。sum2段代码的复杂度为 ，sum3段的代码复杂度为 ；根据加法法则，我们只去其中最大量级的复杂度，所以该段代码的时间复杂度为 。

• 乘法法则

  嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，抽象为公式为：

  若 ，，那么

  public int accumulate(int n) {
      int result = 0;
      for (int i = 1; i <= n; i++) {
          result += f(i);
      }
      return result;
  }
  
  private int f(int n) {
      int sum = 0;
      for (int i = 1; i <= n; i++) {
          sum += i;
      }
      return sum;
  }
  

  其中accumulate方法与f方法的时间复杂度都为 ，但是f嵌套在accumulate中，所以整段代码的复杂度就为：

3，常见时间复杂度量级

度量级	大 O 表示
常量阶
对数阶
线性阶
线性对数阶
平方阶
立方阶
指数阶
阶乘阶

• 常见的时间复杂度有常量阶、对数阶、线性阶、线性对数阶以及平方阶，常量阶、线性阶与平方阶在第二节中已经分析，不再赘述；而一些高效的排序算法的时间复杂度就是线性对数阶，如快速排序，归并排序以及堆排序等。

• 对数阶

  我们所熟知的二分查找的复杂度就是 ，以下通过一段代码来分析对数阶复杂度：

  public int test(int n) {
      int res = 1;
      while (res <= n) {
          res *= 2;
      }
      return res;
  }
  

  该段代码是求 的解，更确切的说，是找出 在小于或等于n的范围内最接近n的x的值；其中 ，即while循环体内代码要执行 次，即其时间复杂度为 。

  若把循环体内代码 res *= 2 改为 res *= 3 ，不难分析出其时间复杂度就变为 ；但是为什么所有对数阶的时间复杂度都统一表示为 ？

  首先我们先复习对数换底公式:
  
  则
  
  所以 ，因为为常数项，所以该项可以忽略，因此；所以无论对数以哪个数为底，最后都可以转化为一个常数项与以2为底的对数相乘，因此在对数阶时间复杂度的表示方法里，就忽略对数的底，统一表示为

• 

  此种表示形式的时间复杂度是由两个数据规模来决定的

  public int accumulate(int m, int n) {
      int sum1 = 0;
      for (int i = 1; i <= m; i++) {
          sum1 += i;
      }
  
      int sum2 = 0;
      for (int i = 1; i <= n; i++) {
          sum2 += i;
      }
  
      return sum1 + sum2;
  }
  

  由于我们不能事先知晓m与n哪个量级大，所以就不能简单的利用加法规则取其最大量级，那么像这种代码的时间复杂度就为 。

  public int accumulate(int m, int n) {
      int sum = 0;
      for (int i = 1; i <= m; i++) {
          for (int j = 1; j <= n; j++) {
              sum += i * j;
          }
      }
      return sum;
  }
  

  而类似上述代码依然可以使用乘法法则，其时间复杂度为

4，最好、最坏、平均和均摊时间复杂度

以下将通过一段代码来讲述这几个时间复杂度：

public class Test {
    private int[] array = new int[5];
    private int N = 0;

    public void push(int item) {
        if (N == array.length) {
            resize(2 * array.length);
        }
        array[N++] = item;
    }

    private void resize(int size) {
        int[] temp = new int[size];
        for (int i = 0; i < N; i++) {
            temp[i] = array[i];
        }
        array = temp;
    }
}

上述代码是用数组模拟一个栈的部分代码，其中push表示压栈操作，resize表示对数组进行扩容的操作；当压入栈中的元素数量达到数组的容量时，就定义一个容量为之前两倍的新数组temp，将旧数组array中的元素复制到新数组中，然后将array指向temp。

• 最好时间复杂度：最理想的情况下，当前栈中元素数量比数组的容量小，此时就直接执行代码块array[N++] = item;，即此时的时间复杂度为 。

• 最坏时间复杂度：最糟糕的情况下，当前栈中元素数量与数组的容量相等，此时就要执行resize方法进行扩容了，进入循环体，执行N次复制操作，此时的时间复杂度为 。

• 平均时间复杂度：

  • 当栈中元素小于数组容量时，此时进行压栈就有N中情况，且每种情况的时间复杂度为 ；当栈中元素与数组容量相等时，此时进行压栈就只有一种情况了，要进行扩容操作，这种情况的时间复杂度为 ；则总共有N+1中情况，对其取平均值：
    
    在大 标记法中，可以省略系数与低阶项，所以其平均时间复杂度为

  • 下面使用概率来分析，由于有N+1中情况，每种情况的发生概率为 ，则其平均时间复杂度为：
    

• 均摊时间复杂度：是一种特殊的平均时间复杂度，根据上述代码，每出现一次扩容操作时，即此时压栈的时间复杂度为 ，那么后面的N次压栈操作的时间复杂度均为 ，前后是连贯的，因此将 平摊到前N次上，得出均摊时间复杂度为 。