学过的东西总是要还给老师的……..
重学数据结构与算法……我觉得甚至可以有机会开一个“那些年还给老师的知识”或者“专业课重修”系列。明明区块链还没有搞清楚，貌似工作上以后还要对接AI的测试了。😔慢慢找人慢慢来吧，这个着急也没用，还是要一步一个脚印来。AI是机器人学习算法呗，那我从算法搞起。不过也是恰好同事发现了这个课程，推广期间只要一元钱。买不了吃亏，买不了上当。买了就学下去吧，反正现在已经都还给老师了。
目前打算是整体规划先按照课程来，课程每周更新两讲。我这学了就一并做下笔记。笔记尽量做下精简和过滤，但是希望让人能读懂。说白了就是记些24K纯干货吧。
模块一：代码效率优化方法论
算法的一个目标是为了完成代码效率的优化，那么衡量程序运行效率的标准是什么呢？复杂度是一个重要指标。程序的本质就是对数据的加工。算法就是用一个更简单的方式去完成数据的加工。复杂度越低，方式就越简单，运算所执行的行数就少百度一下“二分查找算法”可以帮助理解。
我们可以将复杂度拆解为“时间复杂度”（消耗时间）和“空间复杂度”（消耗存储空间）。而输入的数据量不同，消耗的量也不尽相同。那么最后我们可以把程序的复杂度抽象为O(f(n))。表示复杂度是一个关于输入数据量n的函数。比如，O(n)表示复杂度与n线性相关；O(logn)表示复杂度与n对数相关。又是重学系列线性代数和高数。说实在的，我没太懂，但是目前我理解线性相关是直线，对数相关是曲线
复杂度的计算方法遵循以下几个原则：
- 复杂度与常系数无关。比如O(n)和O(2n)表示的复杂度相同，可以解释为后者是前者执行了两遍的结果，但是复杂度是相同的。
- 多项式级的复杂度相加的时候，选择高者作为结果。比如O(n²)+O(n)和O(n²)表示的是相同的复杂度，因为随着n的增加O(n)对于整体的变化曲率的影响将越来越小。
另外O(1)是一个特殊的复杂度，表示复杂度与输入的数据量无关。
对于数组反序的操作，可以用循环反向进行一轮赋值，也可以前后两两互换。所以对于同一问题，采用不同的编码方法，对时间和空间的消耗是有可能不一样的。时间复杂度与代码的结构关系紧密，空间复杂度与数据结构的设计有关。
关于复杂度的经验性结论：
- 一个顺序结构的代码，时间复杂度是O(1)。
- 二分查找等采用二分策略的时间复杂度都是O(logn)。
- 一个for循环，时间复杂度是O(n)。
- 两个顺序的for循环，时间复杂度是O(n)+O(n)=O(2n)，也是O(n)。
- 两个嵌套的for循环，时间复杂度是O(n²)。
代码效率优化的最终目标：要采用尽可能低的复杂度去完成一段代码的开发。
代码效率优化的核心定理：
- 时间昂贵，空间廉价。由于代码效率的瓶颈会发生在时间或者空间两个方面。空间可以花钱买，时间买不来，故如是。
- 数据结构连接时空。程序开发中，连接时间和空间的桥梁是数据结构。如立交桥较十字路口，用空间换取了时间。
完成程序设计并进行代码效率优化的步骤：
- 暴力解法。在不考虑空间和时间的前提下，完成功能的实现。
- 剔除无效操作。将代码中无效的计算和存储剔除，从而降低时间和空间复杂度。
- 时空转换。设计合理的数据结构，完成时间复杂度向空间复杂度的转移。
下面举一个具体的例子。假设有任意多张面额为 2 元、3 元、7 元的货币，现要用它们凑出 100 元，求总共有多少种可能性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//暴力解法
public class MyClass {
public static void main(String[] args) {
int count = 0;
for (int i = 0; i < (100 / 7); i++) {
for (int j = 0; j < (100 / 3); j++) {
for (int k = 0; k < (100 / 2); k++) {
if (((i * 7) + (j * 3) + (k * 2)) == 100) {
count += 1;
}
}
}
}
System.out.println(count);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//剔除无效操作
public class MyClass {
public static void main(String[] args) {
int count = 0;
for (int i = 0; i < (100 / 7); i++) {
for (int j = 0; j < (100 / 3); j++) {
if (((100 - (i * 7) - (j * 3)) % 2) == 0) {
count += 1;
}
}
}
System.out.println(count);
}
}
第二个例子，查找出一个数组中，出现次数最多的那个元素的数值。例如，输入数组 a = [1,2,3,4,5,5,6 ] 中，查找出现次数最多的数值。从数组中可以看出，只有 5 出现了 2 次，其余都是 1 次。显然 5 出现的次数最多，则输出 5。
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
//暴力解法
public class MyClass {
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4, 5, 5, 6 };
int val_max = -1;
int time_max = 0;
int time_tmp = 0;
for (int i = 0; i < a.length; i++) {
time_tmp = 0;
for (int j = 0; j < a.length; j++) {
if (a[i] == a[j]) {
time_tmp += 1;
}
if (time_tmp > time_max) {
time_max = time_tmp;
val_max = a[i];
}
}
}
System.out.println(val_max);
}
}
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
//时空转换
import java.util.HashMap;
import java.util.Map;
public class MyClass {
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4, 5, 5, 6 };
Map<Integer, Integer> d = new HashMap<>();
for (int i = 0; i < a.length; i++) {
if (d.containsKey(a[i])) {
d.put(a[i], d.get(a[i]) + 1);
} else {
d.put(a[i], 1);
}
}
int val_max = -1;
int time_max = 0;
int count = 0;
for (Integer key : d.keySet()) {
if (d.get(key) > time_max) {
time_max = d.get(key);
val_max = count;
}
count++;
}
System.out.println(d);
}
}
模块二：数据结构基础
—收工先，2020年6月8日23点51分
