时间复杂度与空间复杂度

名词解释

  算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

  时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，记做T(n) = O(f(n))，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

  空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

时间复杂度计算示例

以下函数共执行 (n+1)+n+1 = 2n+2 次，根据上述名词解释，可记做 T(n) = 2n+2，即 f(n) = 2n + 2，省略低阶项与首项系数可得 f(n) = n，所以该函数的时候复杂度为 O(n)。由于时间复杂度描述的不是函数执行的具体时间，而是表示算法的变化趋势，所以我们主要关注函数中对函数运行时间影响最大的项，因此可以省略低阶项与首项系数，例如一个函数的执行次数为 n^2 + n^3，我们可省略 n^2，其时间复杂度为 O(n^3)。

private int test(){
  for(int i = 0; i < n; i++){    //此处会执行n+1次
    System.out.println("Hello World!");    //此处会执行n次
  }
  return 1;    //此处会执行1次
}

常见时间复杂度（以下复杂度以升序排列）

• 常数复杂度：O(1)
• 对数复杂度：O(log n)
• 常数对数阶：O(n log n)
• 线性时间复杂度：O(n)
• 平方：O(n^2)
• 立方：O(n^3)
• 指数：O(2^n)
• 阶乘：O(n!)

此图来自“极客时间”

代码示例

• O(1)：

int i = 0;
System.out.println(String.valueOf(i));
System.out.println("one");

• O(log n)：

//由于在循环x次之后，i将大于或等于n跳出循环，即 2^x = n，x = logn，所以时间复杂度为O(logn)
for(int i = 0; i < n; i ++){
  i *= 2;
  System.out.println("i = " + i);
}

• O(n log n)：

for(int i = 0; i < n; i++){
  while(i <= n){
    i = i * 2;
    System.out.println("i = " + i);
  }
}

• O(n)：

for(int i = 0; i < n; i++){
  System.out.println("i = " + i);
}

• O(n^2)：

for(int i = 0; i < n; i++){
   for(int j = 0; j < n; j++){
      System.out.println("i = " + i + “ ”+ “j = ” + j);
   }
}

• O(n ^3)：

for(int i = 0; i < n; i++){
   for(int j = 0; j < n; j++){
      for(int k = 0; k < n; k++){
      System.out.println("i = " + i + “ ”+ “j = ” + j + “ ”+ “k = ” + k);
      }
   }
}

• O(2^n)：

 for(int i = 0; i < Math.pow(2,n); i++){
  System.out.println("i = " + i);
}

• O(n!)：

for(int i = 0; i < factorial(n); i++){
  System.out.println("i = " + i);
}

public long factorial(long l) {
        if (l <= 1) {
            return l;
        } else {
            return l * factorial(l - 1);
        }
    }

空间复杂度计算示例

以下函数进行了两次内存分配，函数所占用的空间不会因为某个变量的变化而变化，也不存在循环，所以该函数的空间复杂度是一个常数，记做 O(1)，比较好理解。

private int test(){
  int i = 1;
  int j = 1;
  i = 2;
  j =3;
}

常见空间复杂度（以下复杂度以升序排列）

• O(1)：以上示例即为 O(1)

• O(n)：

private int test(){
  int[] a = new int[n];
  int i = 1;
  int j = 1;
  i = 2;
  j =3;
}

• O(n^2)：

private int test(){
  int[][] a = new int[n][n];
  int i = 1;
  int j = 1;
  i = 2;
  j =3;
}