复杂度分析是什么

代码的复杂度分为时间复杂度与空间复杂度。

数据结构与算法解决的核心问题就是让代码更“快”、更“省”。具体来说，就是执行的时间尽可能的短，占用的空间尽可能的少。

而代码到底有多“快”、有多“省”，需要对应的衡量标准，时间复杂度就作为代码有多“快”的衡量标准，空间复杂度就作为有多“省”的衡量标准。

对时间复杂度与空间复杂度的计算分析就是复杂度分析了。

为什么需要复杂度分析

我记得我刚接触到时间复杂度这个概念时就有这个疑问：明明可以让代码跑一下来看下它具体的执行时间，以此作为它的时间复杂度不好吗？毕竟这样的跑出来的结果是最为真实的。

这样来作为一段代码的具体执行时间也是可以的，不过不够精确，有很大的局限性。

首先这种直接跑出来的时间非常依赖测试环境，很显然，高端CPU跑一段代码的时间一定是少于普通CPU的。另外，测试结果会受数据规模的影响，在数据量不同的情况下，测试出代码执行的时间一定也是不同的，数据量小的情况下是很难测出一个算法的性能的。

鉴于此，需要从代码本身来分析它的复杂度。从而判断一个算法在时间、空间上的优劣。

时间复杂度分析中的代码执行时间

我们先来看一下如何判断一段代码的执行时间。

int cal(int n) {
  int sum = 0;
  int i = 1;
  int j = 1;
  for (; i <= n; ++i) {
    j = 1;
    for (; j <= n; ++j) {
      sum = sum + i * j;
    }
  }
}

要去除掉环境因素来看一段代码的执行时间，那么首先我们会想到的一定是看一条条语句的执行次数，假定一条语句的执行时间为 t t t，那么代码运行的总时间就是 n ∗ t n*t n∗t， n n n是语句的数量。

当然，这样的方式并不精确，因为一条语句执行的时间我们并不能精确的估计出，且每条语句的执行时间也不相同。

不过，这种分析法的核心就在于抓住次数这一主要矛盾，忽略每条语句所受环境影响造成的执行时间不同的这一次要矛盾。

接着看上述代码：
第2、3、4条语句各执行一次，第5、6条语句各执行 n n n次，第7和第8条语句各执行 n 2 n^2 n2次。所以，总的语句执行次数为 ( 2 n 2 + 2 n + 3 ) (2n^2+2n+3) (2n2+2n+3)。

假设一条语句执行时间为t，那么总的执行时间 T ( n ) = ( 2 n 2 + 2 n + 3 ) t T(n)=(2n^2+2n+3)t T(n)=(2n2+2n+3)t。

大O复杂度表示法表示时间复杂度

前面代码的总的执行时间 T ( n ) = ( 2 n 2 + 2 n + 3 ) t T(n)=(2n^2+2n+3)t T(n)=(2n2+2n+3)t，那么可以看出来， T ( n ) T(n) T(n)是代码中语句执行次数n的函数。用大O复杂度来表示时间复杂度则为 T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2)。

大O复杂度表示的并不是一段代码的真实运行时间，没有实际的测试环境也得不出它的实际运行时间。大O复杂度实际上表示的是代码的执行时间随数据规模增长的变化趋势。这也就是为什么 2 n 2 + 2 n + 3 2n^2+2n+3 2n2+2n+3可以只表示为 n 2 n^2 n2。因为在 n n n非常大的情况下，常量、系数、低阶都是可以忽略不计的。所以说，假设这段代码的总执行时间 T ( n ) = ( 10 n 2 + 9 n + 100 ) t T(n)=(10n^2+9n+100)t T(n)=(10n2+9n+100)t，依然可以用大O复杂度表示法表示为 T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2)。

时间复杂度分析

分析时间复杂度记住三个方法：

只关注循环次数最多的一段代码
加法法则：总复杂度等于量级最大的那段代码的复杂度（多段代码）
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见时间复杂度

O ( 1 ) 、 O ( n ) 、 O ( n 2 ) 、 O ( l o g n ) 、 O ( n l o g n ) O(1)、O(n)、O(n^2)、O(logn)、O(nlogn) O(1)、O(n)、O(n2)、O(logn)、O(nlogn)
O ( 1 ) 与 O ( n ) O(1)与O(n) O(1)与O(n)： O ( 1 ) O(1) O(1)并不是指一段代码中只有一个语句执行了一次，而是语句的执行次数是常量，与输入数据规模无关。而 O ( n ) O(n) O(n)指代码的执行时间与数据规模 n n n成正比关系。

最好、最坏情况时间复杂度

最好、最坏情况时间复杂度顾名思义就是在最好与最坏的情况下，一段程序所会得到的时间复杂度。

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}