时间复杂度

算法

算法是指用来操作数据和解决程序问题的一组方法。对于相同的问题，使用不同的算法，虽然最后的结果一致，但是消耗的时间和资源有很大的区别。

我们从时间和空间两个方面来衡量:

• 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
• 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

时间复杂度

一个算法所消耗的时间，从理论上是不能算出来的，我们需要实际的测试。一个算法花费的时间与算法中语句的执行次数成正比。一个算法中语句执行次数称为语句频度或「时间频度」(记为T(n))。

在时间频度T(n)中，n为问题的规模，当n不断变化的时候，时间频度T(n)也会不断变化。我们通过引入时间复杂度(Time Complexity)的概念来体现T(n)呈现什么样的规律。

算法的时间复杂度也就是算法的时间度量，记作：T(n) = O(f(n))。它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称「时间复杂度」。

O(f(n))表示方法称为「 大O符号表示法 」，又称为渐进符号，是用于描述函数渐进行为的数学符号。

常见的时间复杂度量级有：

• 常数阶

  表示该算法的执行时间(或执行时占用空间)总为一个常量，不论输入数据集是大是小，只要没有循环等复杂结构，那么该代码时间复杂度就是O(1)。

  int one() {
      int i = 1;
      int j = 2;
      return i + j;
  }

  上述代码执行时，它消耗的时间并不会随着代码某个变量增长而增长，无论代码有多长，时间复杂度都是O(1)。

  ---

• 线性阶

  表示一个算法的性能会随着输入数据大小变化而线性变化。

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

  for循环中的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，此类代码时间复杂度用O(n)表示。

  ---

• 平方阶

  表示一个算法的性能会随着输入数据的增长而呈现二次增长，常见于两重循环嵌套。

  void three(int n) {
  	for (i = 1; i <= n; i++) {
          for (j = 1; j <= n; j++) {
              x = j;
              x++;
          }
      }
  }
  
  // 时间复杂度max(O(n^2), O(n))，取O(n^2)
  void three(int n) {
      // 第一部分复杂度O(n^2)
      for (i = 1; i <= n; i++) {
          for (j = 1; j <= n; j++) {
              x = j;
              x++;
          }
      }
      // 第二部分复杂度O(n)
      for (i = 1; i <= n; i++) {
          j = i;
          j++;
      }
  }
  
  // if else 判断语句的总时间复杂度 = max(O(n^2), O(n))
  void three(int n) {
      if (n > 10) {
          // 第一部分复杂度O(n^2)
          for (i = 1; i <= n; i++) {
              for (j = 1; j <= n; j++) {
                  x = j;
                  x++;
              }
          } 
      } else {
          // 第二部分复杂度O(n)
          for (i = 1; i <= n; i++) {
              j = i;
              j++;
          }
      }
  }

  ---

• 立方阶

  表示一个算法的性能会随着输入数据的增长而呈现三次增长，常见于三重循环嵌套。

  void four(int n) {
      for (a = 1; a <= n; i++) {
          for (b = 1; b <= n; j++) {
               for (c = 1; c <= n; j++) {
                	x = c;
              	x++;
               }
          }
      }
  }

  ---

• 指数阶

  表示一个算法的性能会随着输入数据的每次增加而增大两倍。最典型的就是斐波那契数列。

  int fibonacci(int n) {
      if (n <= 1)
          return n;
      // f(n) = f(n - 1) + f(n - 2)；
      return fibonacci(n - 1) + fibonacci(n - 2);
  }

  ---

• 对数阶

  表示一个算法的性能呈指数级增长。

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

  i每次都乘以2，假设循环次数为x，推导出2^x = n，根据大O推导法，可得出下图公式：

  定义：如果一个算法的执行次数是T(n)，那么只保留最高此项，同时忽略点最高此项的系数得到函数f(n)，此时算法时间复杂度就是O(f(n))，简称大O推导法。

  假如 T(n) = n ^ 3 + n^2 + 2，因为n^3增长速度远超n^2，且对精度要求不高，所以此时时间复杂度为：O(n^3)。

  ---

• 线性对数阶

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

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

---

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的一个量度，反映的同样是个趋势，一个算法所需要的存储空间用f(n)表示，S(n) = O(f(n))，n是问题的规模，S(n)表示空间复杂度。

• 常数阶

  如果算法执行所需要的空间不随着某个变量n大小变化而变化，此时算法空间复杂度可以表示为0(1)。

  int one() {
      int i = 1;
      int j = 2;
      int x = i + j;
  }

  ---

• 线性阶

  void two(n) {
      int[] a = new int[n];
      for (i = 1; i <= n; i++) {
          j = i;
          j++;
      }
  }

  上述代码中，只有第一行创建了大小为n的数组，其他代码虽然有循环但是没有创建新的空间，所以空间复杂度为O(n)。

  ---

• 平方阶

  void three(int n) {
      int[] a = new int[n * n];
      for (i = 1; i <= n; i++) {
          j = i;
          j++;
    }
  }

  上述代码，第一行创建了大小为n^2的数组，所以空间复杂度为O(n^2)

---

复杂度速查表

图片来源：https://liam.page/2016/06