算法的时间复杂度与空间复杂度

概述

执行效率是考量一个算法是否高效的主要指标。然而时间、空间复杂度又是衡量算法执行效率的主要维度

一、事后统计法的局限

以前通过统计、监控实际代码的运行就能够获取算法执行的时间和占用的内存大小。这种事后统计方法虽然能够评估算法的执行效率，但还是存在诸多缺陷。

1. 测试结果非常依赖测试环境

   测试环境中硬件配置的不同对测试结果会产生很大的影响。

2. 测试结果受数据规模的影响较大

   对于同一个算法而言，测试数据量的大小不同，其所得出的性能测试结果也会不同。

二、大 O复杂度表示法

如下一段代码：

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

假设每一段代码的执行时间单位为Ｔ，那么第１行代码执行时间为Ｔ，第３行代码由于执行了ｎ次，那么执行时间为ｎＴ所以这段代码的总执行时间为（ｎ＋１）Ｔ，由此可知：所有代码的执行时间T(n)与每行代码的执行次数n成正比。

接下来再看一段代码

public int sum(int n){
     1   int sum = 0;
     2   for (int i = 0 ; i<= n ; ++i){
     3       for (int j = 0 ; j<= n ; ++j){
     4           sum = sum + i*j;
            }
        }
        return sum;
    }

这里每行代码的执行时间单位仍旧为T，那么第1行代码的执行时间为T，第4行代码由于执行了n²次，所以执行时间为n²T。因此，整段代码的执行时间为：（n²+1）T 。

将以上规律总结成一个公式，就是我们所知的大O表达式。

T(n) = O ( f (n) )

其中：T(n)代表代码所执行的时间；n表示数据规模的大小；f(n)表示每行代码执行的次数总和。而公式中的O则表明了代码的执行时间T(n)与 f(n) 表达式成正比。

大O复杂度分析表示法，并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，一般叫作渐进时间复杂度（asymptotic time complexity)，简称时间复杂度。同时，当n趋于无限大的时候，我们就可以忽略公式中的低阶、常量、与系数三部分。只需记录一个最大的量级，如 T(n) = O(2n² + 2n +3) 我们省略掉其中的低阶、常量、与系数所得出的最终结果为：T(n) = O(n²)。因此以上两段代码的时间复杂度就可以记为 ： T(n) = O(n) ；T(n) = O(n²)。

三、时间复杂度分析

1. 只关注循环执行次数最多的一段代码：

   关于这一点，之前的代码示列就是很好的说明，这里不再赘述。

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

   比如如下一段代码：

   public int sum(int n){
           
           int sumOne = 0;
           for (int i = 0; i <= 1000 ; ++i){
      1         sumOne += i;
           }
   
           int sumTwo = 0;
           for (int i= 0; i< n ; ++i){
       2        sumTwo += i;
           }
   
           int sumThree = 0;
           for (int i = 0; i< n ; ++i){
               for (int j = 0 ; j < n ;++j){
       3            sumThree = sumThree + i *j;
               }
           }
   
           return sumOne + sumTwo + sumThree;
       }
   

   这段代码共分为三个部分，分别求sumOne、sumTwo、sumThree。我们可以分别解析每一个部分的时间复杂度，然后再从他们之中选取一个量级最大的作为整段代码的复杂度。

第一段代码执行了1000次，所以其代表的是一个常量级的执行时间，跟n的规模无关，可以将其忽略掉。

第二段代码和第三段代码分别执行了 n 次和 n²次，所以他们的时间复杂度分别为O(n) 和O(n²)。

综合这三段代码的时间复杂度，我们取其中最大的量级，那么整段代码的复杂度就为：O(n²)

因此将上述这个公式抽象一下就可以得出：

如果：T1(n) = O(f(n))，T2(n)=O(g(n))；那么 T(n) = T1(n)+T2(n) = max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))

3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

   如果T1(n) = O(f(n))，T2(n) = O(g(n))；那么 T(n) = T1(n) x T2(n) = O(f(n)) x O(g(n) = O(f(n) x g(n))

public int sum(int n){

        int result = 0;

        for (int i = 0 ; i < n ;++i){
   1         result = result + subSum(n);
        }

        return result;
    }

    public int subSum(int n){
        int subSum = 0;

        for (int j = 0 ; j < n ; ++j){
    2        subSum += j;
        }

        return subSum;
    }

其中：第一段，第二段代码都是执行了n次，时间复杂度都是 T(n) = O(n)。但由于第二段代码是嵌套在第一段代码之中执行的，因此整个代码的时间复杂度应为：T(n) = T1(n) x T2(n) = O(n) x O(n) = O(n²)

四、常见时间复杂度

​

多项式量级	非多项式量级
常量阶O(1)	指数阶O(2n)
对数阶O(logn)	阶乘阶O(n!)
线性阶O(n)
线性对数阶O(nlogn)
平方阶O(n2)、立方阶O(n3)、··· 、k次方阶O(nk)

1. 常量阶 O(1)

   一般来说，只要算法中不存在循环语句、递归语句、即使有成千上万行代码，其时间复杂度仍旧是O(1)

2. 对数阶O(logn)，线性对数阶O(nlogn)

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

   如上一段代码中，i 的取值为 2⁰， 2¹， 2²，···· ， 2^x-1， 2^x 成等比队列。要想知道这段代码执行了多少次，求出 2^x = n 的结果就行。 x = log₂n，所以这段代码的时间复杂度就是 O( log₂n)，这里忽视掉底数，那么所有的对数阶时间复杂度可以表示为O(logn)。

3. O(m+n)、O(m * n)

    public int sum(int m , int n){
   
           int sumOne = 0;
   
           for (int i = 0 ; i<= m ; ++i){
               sumOne += m;
           }
   
           int sumTwo = 0;
   
           for (int j = 0 ; j<= n ; ++j){
               sumTwo += j;
           }
   
           return sumOne+sumTwo;
       }
   

   上述代码中，复杂度取决于两个数据规模 m 与 n，因此无法事先评估m 与 n 谁的量级更大，因此加法法则在这里不适用。因此上段代码的时间复杂度即为O(m+n)。但是乘法法则依旧适用：T1(m) x T2(n) = O(f(m) x f(n))。

五、空间复杂度分析

空间复杂度就是渐进空间复杂度（asymptotic space complexity）,表示算法的存储空间与数据规模之间的增长关系。

 public void initArray(int n){
     1   int[] arr = new int[n];
        for (int i = 0 ; i<= n ; ++i){
            arr[i] = i * i;
        }
    }

如上述代码所示，我们在第一行代码中申请了一个大小为n的int类型数组，除此之外其他的代码都没有占据更多的空间，因此整段代码的空间复杂度就是O(n)，相对于时间复杂度而言，空间复杂度的分析要更为简单。