大O表示法

8/3/2020 大O表示法复杂度分析数据结构与算法

# 程序 = 数据结构 + 算法

# 大O表示法

什么是程序?相信学过编程的人都知道,程序由数据结构和算法构成,想要写出好的的程序,首先得了解数据结构和算法。一切脱离数据结构和算法的程序设计都是耍流氓!

什么样的程序才是好的程序?好的程序设计无外乎两点,"快""省"。"快" 指程序执行速度快,高效,"省" 指占用更小的内存空间。这两点其实就对应 "时间复杂度" 和 "空间复杂度" 的问题。

怎样分析一个程序的时间复杂度和空间复杂度?接下来今天的主角就要登场了!"大O表示法"。"大O表示法" 表示程序的执行时间或占用空间随数据规模的增长趋势。大O表示法就是将代码的所有步骤转换为关于数据规模n的公式项,然后排除不会对问题的整体复杂度产生较大影响的 低阶系数项常数项。乍一看这句话可能不好理解,接下来会详细介绍怎么用 "大O法" 来进行时间和空间复杂度分析。

# 时间复杂度

时间复杂度,又称 "渐进式时间复杂度",表示代码执行时间与数据规模之间的增长关系。

Talking is cheap,show me your code!(不BB,看代码!)

先来看一个简单的栗子,来分析下下面这段代码的时间复杂度:

/**
 * 累加求和
 * @param n 数据规模 n->∞
 * @return
 */
public int sum(int n){
  int sum = 0;
  int i = 0;
  for (;i<n;i++){
    sum = sum + i;
  }
  return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

上面是一个累加求和的方法,假设每条语句的执行时间为单位时间 unit_time,那这个方法对于数据规模 n来说,总的执行时间为多少呢?

很容易看出,第7、8两行代码都只执行一次,各为 unit_time,第9、10两行代码都执行n次,各为 n 倍unit_time,所以总的时间相加得:

T(n)=unit_time + unit_time + n*unit_time + n*unit_time = (2n+2)unit_time

f(n) 来表示代码的执行次数和数据规模的关系,即 f(n)=2n+2当n趋近于无穷大时,f(n)中的常数项对于整个公式的值的影响可以忽略,同样,系数相比数据规模n也可以忽略不计。最后变为 f(n) = n ,即总的执行时间T(n)与数据规模n成正比。上面的分析方法就是 "大O表示法" 的主要思想,用公式来表示就是:

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

  • n:数据规模,通俗点说就是函数中的那个变量n

  • f(n):代码总的执行次数和数据规模的关系

  • T(n):代码的执行时间(并不是代码实际的执行时间,这里表示代码执行时间和数据规模之间的关系)

看到这大概对大O分析法有了一定的理解吧!下面来详细介绍时间复杂度的分析方法。

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

拿上面那个例子来说,第7、8行代码与数据规模无关,执行次数最多的在第9、10行代码,所以只需要关注循环这一部分。利用大O分析法可以知道上面累加求和例子的代码时间复杂度为O(n).

下面再来看一个栗子:

/**
 * 只关注循环次数最多的那一段代码
 * @param n 数据规模 n->∞
 * @return
 */
public int sums(int n){
  int sum = 0;
  int sum1 = 0;
  for (int i=0;i<n;i++){
    sum = sum + i;
  }
  for(int j=0;j<2*n;j++){
    sum1 = sum1 + j;
  }
  return sum+sum1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

依然拿上面累加求和这个例子,不过这次返回的是数据规模 n 累加和数据规模2倍累加的和。该方法中有2处循环部分,第9、10行和第12、13行。可以看出来,这两处都有循环的部分,但是下面循环执行次数比上面多。根据上面的原则,我们只需要关注循环执行次数最多的那部分代码,即只需要关注2倍累加求和的部分。按照上面大O分析法可以知道,这段代码的时间复杂度为O(n)。

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

首先,来了解一下量级的概念。下面是一些常见的复杂度量级及其大O法的表示。

常量阶(O(1)):代码片段执行时间不随数据规模n的增加而增加,即使执行次数非常大,只要与数据规模无关,都算作常量阶,记作O(1)

按量级递增排序:常量阶O(1)) < 对数阶O(logn) < 线性阶O(n) < 线性对数阶O(nlogn) < 平方阶O(n²)...立方阶O(n³)...k方阶 < 指数阶O(2^n) < 阶乘阶O(n!)

其中,O(2^n)和O(n!)为非多项式量级,其他的为多项式量级。我们把时间复杂度为非多项式量级的算法问题叫作NP(Non-Deterministic Polynomial,非确定多项式)问题。

下面请看一段代码:

/**
 * 加法法则:总复杂度等于量级最大的那段代码的复杂度
 * @param n 数据规模 n->∞
 * @return
 */
public int maxItem(int n){

  // part1: 执行1000次循环
  int i = 0;
  int sum1 = 0;
  for (;i<1000;i++){        
    sum1 = sum1 +i;
  }

  // part2: 执行n此循环
  int j = 0;
  int sum2 = 0;
  for (;j<n;j++){            
    sum2 = sum2 +j;
  }

  // part3: 嵌套执行n次循环
  int sum3 = 0;
  for (int k=0;k<n;k++){            
    for (int l=0;l<n;l++){
      sum3 = sum3 + l;
    }
  }

  return sum1+sum2+sum3;
}
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
26
27
28
29
30
31

代码中有三部分,来分别分析每一部分的时间复杂度。第一部分循环执行1000次,与数据规模n无关,即使执行10000次,100000次都算作常量阶,时间复杂度为O(1)。

第二部分循环执行n次,与数据规模n成正比,时间复杂度是线性阶O(n)。

第三部分有两层循环,每层循环都执行n次,总共执行n*n=n²次,时间复杂度为平方阶O(n²)。

所以这段代码总的时间复杂度记作T(n) = O(1)+O(n)+O(n²),按照加法法则,只取最大量级的的复杂度,即整段代码的时间复杂度为O(n²)。

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

依旧来看一段代码:

/**
 * 外层方法
 * @param n 数据规模
 * @return
 */
public int outSum(int n){
  int i = 0;
  int sum = 0;
  for (;i<n;i++) {
    // 这里调用inSum()方法累加求和
    sum = sum + inSum(i);
  }
  return sum;
}

/**
     * 里层方法
     * @param n 数据规模
     * @return
     */
public int inSum(int n){
  int i = 0;
  int sum = 0;
  for (;i<n;i++) {
    sum = sum + i;
  }
  return sum;
}
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
26
27
28

不难分析出,单看外层和里层循环,时间复杂度均为O(n)。二者嵌套一起就可以用到乘法法则,总的时间复杂度为O(n*n)=O(n²)。其实这里就是循环嵌套,总的执行次数为内外执行次数的乘积。

# 空间复杂度

空间复杂度,也称渐进空间复杂度,表示代码存储空间与数据规模之间的增长关系。

空间复杂度相对于时间复杂度来说,要简单的多了。下面看一个简单的栗子:

/**
 * 空间复杂度分析
 * @param n 数据规模
 */
public void space(int n){
  int i = 0;
  int[] arr = new int[n];
  for (;i<n;i++) {
    arr[i] = i;
  }
}
1
2
3
4
5
6
7
8
9
10
11

第6行申请一个空间存储变量 i ,由于该空间和数据规模无关,属于常量阶的空间复杂度,可忽略不计。

第7行申请一个大小为 n 的空间存储数组 arr,空间复杂度与数据规模成正比,为O(n)。所以整段代码空间复杂度就是O(n)。

常用的空间复杂度就是O(1)。像O(n²)、O(n³)、O(logn)、O(nlogn)这样的空间复杂度平时都用不到。