时间复杂度分析-上

发表于 | 分类于 | | 浏览 次
字数统计: 2.9k | 阅读时长 ≈ 10

参考文章来源：极客时间

链接地址：时间复杂度分析-上

时间和空间复杂度是衡量一个算法执行效率的标准。

数据结构与算法跟时间空间复杂度是密不可分的，复杂度分析是算法的精髓，掌握了它后学习数据结构和算法就会有事半功倍的效果。

为什么需要复杂度分析

把代码跑一遍，监控代码运行时间、内存使用情况不久可以大致估算出算法执行的时间和内存占用大小吗？为什么还要分析算法的时间和空间复杂度。

测试结果依赖测试环境

首先，测试中硬件的不同对测试结果的影响非常大，单纯靠在硬件上跑代码的方式不能客观衡量一个算法的性能。比如用一个i9的处理器和一个奔腾处理器运行同一个算法，肯定i9的处理速度更快，但是代码是同一段代码啊，怎么衡量代码复杂度呢？还有就是两个算法在一台计算机上的执行速度与在另一台计算机上执行速度可能差别很大。

测试结果手数据规模的影响很大

对于同一个算法，待排序的数据有序度不一样的情况下，执行排序的时间会相差很多，这就是与数据量有关。极端情况下如果数据已经有序，那么排序算法不需要做任何操作，执行时间就会非常短。另外如果测试数据规模很小，测试结果很可能不能真实反映算法的性能。比如小规模的数据排序，插入排序可能反倒比快速排序要快。

大O复杂度表示法

算法的执行效率通俗地讲就是算法代码的执行时间。比如下面这段代码：

1
2
3
4
5
6
7
8
int cal(int n) {
  int sum = 0;
  int i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}

从CPU角度来看，这段代码每一行都执行类似的操作：读数据-运算-写数据。尽管每行代码都对应CPU执行的个数、执行的时间都不一样，但是，我们这里只做粗略估计，所以可以假设每行代码执行的时间都一样，为unit_time。在这个假设基础上，这段代码的总执行时间是多少呢？

第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第4、5行都运行了n遍，所以需要2nunit_time 的执行时间，所以这段代码总的执行时间就是(2n+2)\unit_time。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

可以把规律总结成一个公式：

O

这里面T(n)表示代码执行的时间，n表示数据规模的大小；f(n)表示每行代码执行的次数总和。因为这是一个公式，所以用f(n)表示，公式中的O表示代码的执行时间T(n)与f(n)表达式成正比。

第一个例子中的T(n) = O(2n+2)，第二个例子中的T(n) = O(2n^2+2n+3)。这就是大O时间复杂度表示法。大O时间复杂度并不是实际上代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫做渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。

当n很大时，可以想像成10000、100000，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，只需要记录一个最大量级就可以了，上面两段代码的时间复杂度可以记为：T(n)=O(n),T(n) = O(n^2).

时间复杂度分析

下面说一下时间复杂度的分析方法。

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

时间复杂度只表示的是一种随着数据量增加算法执行时间的变化趋势，通常会忽略掉公式中的常量、低阶、系数，在分析一个算法，一段代码的时间复杂度时候，也只需要关注循环执行次数最多的那一段代码就可以了，这段核心代码执行次数n的量级就是整段代码时间复杂度的关键。

举个栗子：

1
2
3
4
5
6
7
8
int cal(int n) {
  int sum = 0;
  int i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}

第2、3行代码都是常量级的执行时间，与n的大小无关，所以对于复杂度并没有影响，循环执行次数最多的是4、5行，所以这块代码是分析的重点。这两行代码被执行了n次，所以总的时间复杂度就是O(n)。

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

再举个栗子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

这段代码分三个部分，分别求sum_1, sum_2, sum_3。我们分别分析一下每一部分的时间复杂度，然后把他们放到一起，再取一个量级最大的作为整段代码的复杂度。

首先sum_1的时间复杂度，这段代码执行了100次，所以是一个常量的执行时间，跟n的规模无关。

这里需要强调一下，即使这段代码执行了10000次，只要是一个已知的常熟，跟n无关，照样时常量级的执行时间。当n无限大时，就可以忽略，尽管对代码的执行时间有很大影响，但是回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，我们都可以忽略，因为它本身对增长趋势并没有影响。

第二段和第三段代码的时间复杂度分别是O(n)和O(n²)，这很容易分析出来。

综合三段代码，取量级最大的O(n²)，所以整段代码的时间复杂度就是O(n²)。

  1. 乘法法则：嵌套代码的时间复杂度等于枪套内外代码复杂度的乘积。

举个栗子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int cal(int n) {
   int ret = 0; 
   int i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i);
   } 
 } 
 
 int f(int n) {
  int sum = 0;
  int i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }

单独看cal()函数，那4~6行的时间复杂度就是整个函数的时间复杂度，但是cal函数不是一个简单的操作，它还调用了f函数，而f函数的时间复杂度也是O(n)，所以整个cal函数的时间复杂度就是T(n) = T1(n) T2(n) = O(nn) = O(n²)。

几种常见时间复杂度实例分析

虽然代码千差万别，但是常见的复杂度量级并不多，一般都有一下几种：

复杂度量级

这些量级可以分为两类：多项式量级和非多项式量级。其中非多项式量级只有两个：O(2^n) 和 O(n!)。

当数据规模越来越大时，非多项式量级算法执行时间急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法效率很低。下面主要看一下集中常见的多项式时间复杂度。

O(1)

首先，O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如下面这段代码，即便有3行，它的时间复杂度也是O(1)，而不是O(3)。

1
2
3
int i = 8;
int j = 6;
int sum = i + j;

只要代码的执行时间不随n的增大而增长，这样的代码的时间复杂度我们都记作O(1)，一般情况下，只要算法中不存在循环语句，递归语句，即使有成千上万行的代码，其时间复杂度都是O(1)。

O(logn)、O(nlogn)

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。

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

根据前面的分析，第三行代码是执行次数最多的，所以我们只要计算出这行代码被执行了多少次，就能知道争端代码的时间复杂度。变量i从1开始，每循环一次就乘以2，当大于n时，循环结束。这里变量i的取值就是一个等比数列，如果列出来就是这样：

i取值

这里x=logn，所以整段代码时间复杂度就是O(log2n)。

不管log以多少为底，都记作O(logn)。

另外O(nlogn)表示一段代码的时间复杂度是O(logn)，循环执行n遍，时间复杂度就是O(nlogn)了，而且O(nlogn)是一种非常常见的时间复杂度，归并排序、快速排序的时间复杂度都是O(nlogn)。

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

代码中m和n是两种数据规模，我们实现无法评估m和n谁的量级大，所以时间复杂度表示为O(m+n)。乘法法则继续有效。

空间复杂度分析

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

举例子：

1
2
3
4
5
6
7
8
9
10
11
void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

跟时间复杂度一样，第二行代码申请了一个空间存储变量i，但是它是常量阶的，跟数据规模无关，所以可以忽略，第3行申请了一个大小为n的int类型数组，除此之外，剩下的代码没有占用更多空间，所以整段代码的空间复杂度就是O(n)。

常见的空间复杂度有O(1)、O(n)、O(n2 )，像 O(logn)、O(nlongn)这样的对数阶复杂度平时都用不到，而且空间复杂度比时间复杂度要容易分析，掌握这些就足够了。

总结

复杂度也叫渐进复杂度，包括时间和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略表示，越高阶复杂度的算法，效率越低。常见的复杂度并不多，从低阶到高阶有O(1)、O(logn)、O(n)、O(nlogn)、O(n²)。

总结

复杂度分析关键在多练，每次看到代码，都先分析一下它的复杂度，最后做到看一眼就能看出其复杂度，对于复杂一些的代码稍微分析一下就能得到它的复杂度。