前言
此篇为本系列第一篇，因此在此说明一些有关信息：
- 本系列主要总结数据结构与算法相关知识。
- 本系列是笔者以B站数据结构与算法课程为学习路线进行学习总结的，有没有讲明白的，可点击 链接 前往B站原视频看看左神是怎么讲的。
- 由于笔者平时Java用的比较多，因此此系列中多以Java语言作为代码实现首选语言，当然数据结构与算法在不同语言中是通用的，差别仅在于不同编程语言中数据类型可能不同，同一个数据结构或算法实现代码不同，但思路都是相同的。
- 数据结构与算法是重实践的知识，勤加练习手敲代码才能掌握的更快，用的更灵活。
复杂度
时间复杂度常作为衡量算法性能优劣的一项指标，在数据量N越大时越具有参考性。
要理解时间复杂度首先要知道常数操作是什么？
常数操作
常数操作指：一项操作的完成时间与数据量没有关系，就称为常数操作。
例如：访问数组元素就直接计算偏移量后一次取出数据，而访问链表元素就需要遍历链表元素，从上一个元素中才能找到下一个元素的位置，这就决定了链表访问元素与数据量有关，因此访问数据元素是常数操作，而访问链表元素不是。
时间复杂度的计算
要计算算法时间复杂度，首先要了解算法的计算过程，分辨出此算法包含了哪些常数操作，这些常数操作都执行了多少遍，特别注意那些执行了N遍的操作(N表示数据量)，将总的操作次数写成一个表达式，表达式中最高阶除系数之外的部分记为 f(N) ，则称 O(f(N)) 为此算法的时间复杂度，例如计算出来常数操作数量表达式为 10N^2+2N+3，则时间复杂度为 O(N^2)
简单来说，计算时间复杂度就关注算法中哪些部分执行了N次或N的幂次，最高项往往在这些中，关注循环结构，往往循环结构中会产生遍历的操作，很可能与数据量N有关，那些执行次数比较少的与N无关的常数操作就不用管了，不会影响到时间复杂度的计算。
时间复杂度的比较
表达式中次方越小时间复杂度越低，理论上算法耗时更少。
表达式相同时，时间复杂度表达式就不具有参考价值了，直接比较不同数据样本下实际的运行时间，即 常数项时间 ，直接跑代码运行一遍效果最快。
空间复杂度的计算
空间复杂度是算法计算过程中需要另外开辟变量的操作复杂度，当算法只需要个别几个变量就能完成算法时认为空间复杂度为 O(1) ，更高复杂度举个例子：需要开辟与数据量等长的数组才能完成计算时空间复杂度为 O(N)。
递归的时间复杂度
关于递归时间复杂度的计算与一般的时间复杂度计算有点不一样，可以先跳过这部分，在后面学到递归过程后再回过头来看递归的时间复杂度计算能更容易理解。
如果用递归解决问题时，原问题拆解为子问题的过程将数据量是等分的(类似二等分、三等分…)，则可以使用 master公式 来辅助递归求解问题的时间复杂度求解问题，master公式
master公式
T(N) = a*T(N/b)+O(N^d) 中参数的理解
| 项 |
解释 |
N |
原问题的数据规模 |
a |
在一层递归中调用递归函数的次数 |
b |
原问题划分的直接子问题数 |
O(N^d) |
在一层递归中除了调用递归函数其他部分的时间复杂度 |
举个例子，在上面递归求解数组最大值的问题中，master公式为: T(N)=2*T(N/2)+O(1)
在得到问题对应的 master公式 后就可以根据规则求解时间复杂度了(tips:log(b,a)指log以b为底的a)：
log(b,a) > d 则时间复杂度为O(N^log(b,a))log(b,a) < d 则时间复杂度为O(N^d)log(b,a) = d 则时间复杂度为O(N^d*logN)
注意:master公式是求解时间复杂度过程中的一个工具，而不是最终的时间复杂度
二分查找的时间复杂度
二分查找常用在有序数据中查找数据，时间复杂度是 O(log以2为底的N) 常写作 O(logN)，不特别指出底数在时间复杂度这里就默认是以2为底数
但是二分查找并不是不能用在无序数组的查找中，这还要结合题目的要求和数据的分布来看二分查找是否可用，例如无序数组中查找局部最小值就可以用二分查找
对数器
在进入排序算法学习之前，先了解一种测试方法，叫做对数器，在后面自己书写排序方法后可以通过对数器验证结果是否正确。
原理是：使用同一组数据在两种方法中分别测试，一种方法是要测试的，一种方法是作为对照组标准的，比较结果是否相同，来达到在本地测试方法的目的，例如检查自己写的插入排序是否正确，可以与java语言提供的 Arrays.sort() 方法对比，下面代码中还包含常用的随机数组生成模块
对数器的使用示例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
| import java.util.Arrays;
public class Test {
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int)(Math.random() * (maxSize))+1];
for(int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random() * (maxValue+1))-(int)(Math.random() * maxValue);
}
return arr;
}
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
public static int[] copyArray(int[] arr) {
if(arr==null) {
return null;
}
int[] res = new int[arr.length];
for(int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
public static boolean isEqual(int[] arr1, int[] arr2) {
if(arr1 == null || arr2 == null) {
if((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)){
return false;
}
return true;
}
if(arr1.length != arr2.length) {
return false;
}
for(int i = 0; i < arr1.length; i++) {
if(arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int testTimes = 100000;
int maxSize = 100;
int maxValue = 1000;
boolean success = true;
for(int i = 0; i<testTimes; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
Sort_InsertSort.insertSort(arr1);
comparator(arr2);
if(!isEqual(arr1,arr2)) {
success = false;
break;
}
}
System.out.println(success ? "good job!" : "there is something wrong!");
}
}
|
比较器
比较器的使用也能帮助你在编写排序算法时方便测试，比较器的使用能方便比较过程和排序过程，特别是用于自定义对象的比较，在Java中我们称之为比较器，在C++中则称为重载运算符，完成的功能是一样的
在Java中要建立一个比较器的步骤如下：
- 自定义比较器类，实现
java.util.Comparator接口
- 在比较器类中要实现
compare()方法
- compare()方法默认规则:
- 比较结果中先是第一个参数时返回正数
- 比较结果中先一个是第二个参数时返回负数
- 比较结果为相等时返回0
- 在要排序的函数中，将比较器类的实例化对象作为参数即可
下面是自定义类的对象比较器，在示例中通过调用不同的比较器实现不同的排序
比较器示例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
| import java.util.Arrays;
import java.util.Comparator;
public class StudentCompare {
private int studentID;
private int age;
public StudentCompare() {
studentID = 0;
age = 18;
}
public StudentCompare(int id, int age) {
this.studentID = id;
this.age = age;
}
public static class IDComparator implements Comparator<StudentCompare>{
public int compare(StudentCompare student1, StudentCompare student2) {
return student1.studentID-student2.studentID;
}
}
public static class AgeComparator implements Comparator<StudentCompare>{
public int compare(StudentCompare student1, StudentCompare student2) {
return student1.age-student2.age;
}
}
public static void studentPrint(StudentCompare student) {
System.out.println("studentID="+student.studentID+" "+"age="+student.age);
}
public static void studentPrint(StudentCompare[] students) {
for(int i=0; i<students.length; i++) {
System.out.println("studentID="+students[i].studentID+" "+"age="+students[i].age);
}
}
public static void main(String[] args) {
StudentCompare student1 = new StudentCompare(1, 18);
StudentCompare student2 = new StudentCompare(2, 17);
StudentCompare[] students = {student1, student2};
studentPrint(students);
Arrays.sort(students, new IDComparator());
studentPrint(students);
Arrays.sort(students, new AgeComparator());
studentPrint(students);
}
}
|
微信
支付宝
