沧海一粟

天下事有难易乎?为之,则难者亦易矣;不为,则易者亦难矣。

0%

数据结构 复杂度分析

数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,如何让代码更省存储空间。所以,执行效率是算法一个非常重要的考量指标。

(1) 为什么需要复杂度分析

把代码跑一遍,通过统计、监控,就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢?

这种评估算法执行效率的方法是正确的,叫事后统计法。但是,这种统计方法有非常大的局限性。

  1. 测试结果非常依赖测试环境
  2. 测试结果受数据规模的影响很大

在大学刚学C语言的时候,老师交给我们一个任务,根据高斯公式计算π的值,分别精确到第六位、第七位、第八位 …,下课后直接在图书馆写代码计算,计算结果精确到第六位的时候特别快,刚点运行就计算完了,花费几ms,计算第七、八、九位也很快,不超过3s,但是精确到第十位的时候,运行了30s后,听到电脑风扇 呼呼 地响了。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

/**
* <pre>
*
*
* 计算π
*
* 无穷级数法
* 莱布尼兹级数:π/4 = 1- 1/3 + 1/5 - 1/7 + 1/9 … (收敛很慢)
* 马青公式:π/4 = 4(1/5-(1/5)³/3+(1/5)^5/5-(1/5)^7/7+……)+(1/239-(1/239)³/3+(1/239)^5/5-(1/239)^7/7+……)(du收敛较快,每计zhi算一项可得到π的1.4位十进制精度)
*
*
*
* 含圆周率的公式列表- 维基百科,自由的百科全书 zh.wikipedia.org › zh-hans › 含圆周率的公式列表 https://zh.wikipedia.org/zh-hans/%E5%90%AB%E5%9C%86%E5%91%A8%E7%8E%87%E7%9A%84%E5%85%AC%E5%BC%8F%E5%88%97%E8%A1%A8
* 【并行计算】六种方法计算圆周率 http://littledva.cn/article-16/
* http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/piforms.html
*
* Java小程序计算圆周率代码 http://www.uxys.com/html/JavaKfjs/20170911/15192.html
* π后100位的计算PI https://blog.csdn.net/zhanbiane/article/details/56488694
*
* </pre>
*
* @author weikeqin
* @date 2020-07-18 09:09
*/
public class CalculatePiApproximation {

/**
* @param args
*/
public static void main(String[] args) {

CalculatePiApproximation c = new CalculatePiApproximation();
double preciseCount = 1E-10;
c.caclPi1(preciseCount);

}

/**
* <pre>
*
* 利用公式 π/4 ≈ 1 - (1/3) + (1/5) - (1/7) + ... ,
* 编写程序计算π的近似值,
* 直到最后一项的绝对值小于0.000001
*
* 精确到小数点后几位
* 1e-6 = 1 * 10^(-6)
*
* 无穷级数法
* 莱布尼兹级数:π/4 = 1- 1/3 + 1/5 - 1/7 + 1/9 … (收敛很慢)
* 马青公式:π/4 = 4(1/5-(1/5)³/3+(1/5)^5/5-(1/5)^7/7+……)+(1/239-(1/239)³/3+(1/239)^5/5-(1/239)^7/7+……)(du收敛较快,每计zhi算一项可得到π的1.4位十进制精度)
*
* </pre>
*
* @param preciseCount 精确到小数点后几位 1E-6
* @return
*/
public double caclPi1(double preciseCount) {
long t1 = System.currentTimeMillis();
int symbol = 1;
// 当前分数
double term = -1.0;
double pi = 0.0;
int i = 1;
int count = 0;

while (Math.abs(term) > preciseCount) {
count++;

// 1/1 1/3 1/5
term = 1.0 * symbol / i;
// 1 -1
symbol = -symbol;
// 1 - 1/3 + 1/5 - 1/7
pi += term;
i += 2;

}

pi *= 4;

long t2 = System.currentTimeMillis();

System.out.println("pi:" + pi);
System.out.println("loop count:" + count);
System.out.println("cost " + (t2 - t1) + " ms");
return pi;
}

}

(2) 时间复杂度

从 CPU 的角度来看,这段代码的每一行都执行着类似的操作:读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样,但是,我们这里只是粗略估计,所以可以假设每行代码执行的时间都一样,为 unit_time。

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

1
2
3
4
5
6
7
8
9
10
/**
* 两数之和
*
* @param x
* @param y
* @return
*/
public int add(int x, int y) {
return x + y;
}
1
2
3
4
5
6
7
8
/**
* @return
*/
public int sum() {
int x = 0;
int y = 1;
return x + y;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 等差数列的求和
* 公差为1
*
* @param x
* @return
*/
public int seqSum(int x) {
int sum = 0;
for (int i = 0; i < x; i++) {
sum += i;
}
return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @param x
* @return
*/
public int sum2(int x) {
int sum = 0;
for (int i = 0; i < x; i++) {
for (int j = 0; j < x; j++) {
sum += j;
}
}
return sum;
}

大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

  1. 只关注循环执行次数最多的一段代码
  2. 加法法则:总复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

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

  1. O(1)
  2. O(logn)、O(nlogn)
  3. O(m+n)、O(m*n)

复杂度量级

O(1) 常数阶
O(logn) 对数阶
O(n) 线性阶
O(nlogn) 线性对数阶
O(n^2) 平方阶
O(n^3) 立方阶
O(n^k) k次方阶

O(2^n) 指数阶
O(n!) 阶乘阶

对于刚罗列的复杂度量级,我们可以粗略地分为两类,多项式量级和非多项式量级。其中,非多项式量级只有两个:O(2n) 和 O(n!)。

我们把时间复杂度为非多项式量级的算法问题叫作 NP(Non-Deterministic Polynomial,非确定多项式)问题。当数据规模 n 越来越大时,非多项式量级算法的执行时间会急剧增加,求解问题的执行时间会无限增长。所以,非多项式时间复杂度的算法其实是非常低效的算法。

(3) 空间复杂度

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

1
2
3
4
5
6
7
8
9
/**
*
*/
public int[] memory1() {
int i = 1;
int[] arr = new int[1];
arr[0] = 1;
return arr;
}

可以看到,申请了一个变量i的存储空间,并且申请了 arr的存储空间。但是它是常量阶的,跟数据规模 n 没有关系,所以空间复杂度是O(1)

1
2
3
4
5
6
7
8
9
10
/**
*
*/
public int[] memory2(int n) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = 1;
}
return arr;
}

可以看到,申请了一个变量i的存储空间,并且申请了 arr的存储空间。arr的大小和n有关系,所以空间复杂度是O(n)

1
2
3
4
5
6
7
8
9
10
11
12
/**
*
*/
public int[][] memory3(int n) {
int[][] arr = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = 1;
}
}
return arr;
}

可以看到,申请了一个变量i的存储空间,并且申请了 arr的存储空间。arr的大小和n有关系,因为是两个循环,所以空间复杂度是O(n^2)

空间复杂度就是 O(1)、O(n)、O(n^2),像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且,空间复杂度分析比时间复杂度分析要简单很多。

References

[1] 《算法基础》 Richard Neapolitan (作者) 贾洪峰 (译者)
[2] 03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
[3] 04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
[4] [算法的时间复杂度和空间复杂度-总结( https://blog.csdn.net/zolalad/article/details/11848739 )