文章目录
1 算法的衡量标准
1.1 算法
解决问题的办法，是一种独立的存在的解决问题的方法和思想，它不依赖于代码。代码只不过是对算法的一种表达和实现。
1.2 数据结构
存储和组织数据的方式
1.3 时间复杂度
在规模量级上对算法的衡量，表示一个算法随着问题规模不断变化的最主要趋势
- 计算规则（6 条）
基本操作：只有常数项，时间复杂度为 O (1）顺序结构：时间复杂度按加法进行计算循环结构、递归结构：时间复杂度按乘法进行计算分支结构：时间复杂度取最大值- 判断一个算法的效率时，往往只需要关注操作数量的
最高次项，忽略系数、低阶及常数项 - 在没有特殊说明的情况下，我们所分析的算法的时间复杂度都是指
最坏时间复杂度（提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。） 函数嵌套，时间复杂度按乘法计算
O (1） 执行次数恒定的计算
1.4 空间复杂度
一个算法在运行过程中临时消耗内存的大小的度量
1.5 算法的复杂度
算法的时间复杂度和空间复杂度的合称
1.6 算法五大特性
①输入：算法具有 0 个或多个输入
②输出：算法至少有 1 个或多个输出
③有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
④确定性：算法中的每一步都有确定的含义，不会出现二义性
⑤可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
1.7 常见时间复杂度
| 执行次数函数举例 | 阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3n2+2n+1 | O(n2) | 平方阶 |
| 5log2n+20 | O(logn) | 对数阶 |
| 6n3+2n2+3n+4 | O(n3) | 立方阶 |
-
时间复杂度曲线
- 所消耗的时间从小到大:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)- 时间复杂度越低，效率越高
- 所消耗的时间从小到大:
2 数据结构
2.1 数据结构
数据对象中数据元素之间的关系 -
- 内置数据结构：list、元组、字典等
- 扩展数据结构：栈、队列等
2.1.1 程序 = 数据结构（问题载体） + 算法
高效的程序需要在数据结构基础上设计和选择算法
2.1.2 元素外置：地址和数据分开存储
- 地址存储占用的内存空间
- 32 位操作系统：
4位 - 64 位操作系统：
8位
- 32 位操作系统：
2.1.3 数据结构
1 线性结构
1.1 顺序表
- 一体式顺序表
- 分离式顺序表
1.2 链表
- 单链表
- 元素域： 存放具体数据
- 链接域： 存放下一个节点的位置
- 元素域： 存放具体数据
1.3 栈
-
1.3.1 特点：
① 一种运算受限的
线性表，仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，相对地，把另一端称为栈底.② 处理数据的时候符合
先进后出（FILO）特点 -
1.3.2 作用：函数里面有可能要使用到局部变量，不能总是用全局变量。而局部变量在函数使用完毕之后就销毁了，那么将局部变量存储在栈中既能不浪费空间又能及时销毁.
-
1.3.3 代码实现
-
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
26
27
28
29
30class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class LinkedStack:
def __init__(self):
# 最上面的元素
self.top = None
def push(self, value: int):
newtop = Node(value)
newtop.next = self.top
self.top = newtop
def pop(self):
if self.top:
value = self.top.data
self.top = self.top.next
return value
if __name__ == "__main__":
stack = LinkedStack()
for i in range(9):
stack.push(i)
for i in range(9):
ele = stack.pop()
print(ele)
-
1.4 队列
-
特点：
① 一种操作受限的
线性表，只允许在表的头部（front）(队头) 进行删除操作，而在表的尾部（rear）（队尾）进行插入操作。② 处理数据的时候符合
先进先出（FIFO）特点 -
作用：
在任务处理类的系统中，先把用户发起的任务请求接收过来存到队列中，然后后端开启多个应用程序从队列中取任务进行处理，队列可以起到了
缓冲压力的作用 -
代码实现
-
列表队列优化
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# 尾部入 头部出
class ArrayQueue:
def __init__(self, capacity):# capacity 容量
# 申请固定长度空间
self.__items = [0]*capacity
self.__capacity = capacity
# 头部指针
self.__head = 0
# 尾部指针(下一个元素添加到这个位置)
self.__tail = 0
def getItmes(self):
return self.__items
def enqueue(self, item):
# 如果存满了,返回False
if self.__head==0 and self.__tail==self.__capacity:
return False
# 没有存满,指针到最后了 需要先把元素往前挪
if self.__tail==self.__capacity:
# 指针到最后了,容量没有满
for i in range(0, self.__tail - self.__head):
self.__items[i] = self.__items[i + self.__head]
# 修改尾部指针
self.__tail = self.__tail - self.__head
# 修改头部指针
self.__head = 0
# 元素添加
self.__items[self.__tail] = item
self.__tail += 1
return True
def dequeue(self):
# 非空
if self.__head != self.__tail:
item = self.__items[self.__head]
# 把头部往后移动1位
self.__head += 1
return item
else:
return None
arrayQ = ArrayQueue(6)
arrayQ.enqueue(10)
arrayQ.enqueue(20)
print(arrayQ.getItmes())
print(arrayQ.dequeue())
print(arrayQ.getItmes())
arrayQ.enqueue(30)
arrayQ.enqueue(40)
arrayQ.enqueue(50)
arrayQ.enqueue(60)
arrayQ.enqueue(70)
print(arrayQ.getItmes()) -
链表实现队列
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# 节点
class Node:
def __init__(self, data, next=None):
# 数据
self.data = data
# 链接域
self.next = next
class LinkedQueue:
def __init__(self):
self.__head = None
self.__tail = None
def enqueue(self, value):
'''入队列'''
new_node = Node(value)
if self.__tail:
# 非空
self.__tail.next = new_node
else:
# 空链表
self.__head = new_node
# 尾部指向新的节点
self.__tail = new_node
def dequeue(self):
if self.__head:
# 头部不为空
# 获取头部元素
value = self.__head.data
# 头部指向原来的下一个节点
self.__head = self.__head.next
if not self.__head:
# 如果头部指向None 链表为空
self.__tail = None
return value
if __name__ == "__main__":
linkQ = LinkedQueue()
linkQ.enqueue(10)
linkQ.enqueue(20)
linkQ.enqueue(30)
print(linkQ.dequeue())
print(linkQ.dequeue())
print(linkQ.dequeue()) -
双端队列
-
特点：
- 一种具有队列和栈的性质的数据结构
- 双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行
- 双端队列可以在队列任意一端入队和出队
2 非线性结构
- 树
3 排序算法
3.1 排序
使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
3.2 算法稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的，否则称为不稳定的。
3.3 排序算法
-
不稳定算法: 选择排序、快速排序、希尔排序、堆排序 -
稳定算法: 冒泡排序、插入排序、归并排序和基数排序
3.3.1 代码实现
1 冒泡排序
-
特点：
重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从从 Z 到 A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成
名字由来：因为越小的元素会经由交换慢慢 “浮” 到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名 “冒泡排序”
-
复杂度分析：
-
最差时间复杂度 :
O(n^2) -
最优时间复杂度 :
O(n)# 遍历一遍发现没有任何元素发生了位置交换，终止排序 -
算法稳定性：稳定算法
-
原地排序：是
-
1 | # n-1+n-2+...+1 |
2 选择排序
-
特点：
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零.
-
复杂度分析：
-
最差时间复杂度 :
O(n^2) -
最优时间复杂度 :
O(n^2) -
算法稳定性：不稳定算法
-
原地排序：是
-
1 | def select_sort(alist): |
3 插入排序
-
特点：
将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。（每步将一个待排序的记录，按排序要求插入到前面已经排序的数据中适当位置上，直到全部插入完为止）
-
复杂度分析：
- 最差时间复杂度:
O(n^2) - 最优时间复杂度:
O(n) - 算法稳定性：稳定的排序方法
- 原地排序：是
- 最差时间复杂度:
1 | def insert_sort(alist): |
4 快速排序
-
特点：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
-
排序流程：
(1) 首先设定一个分界值，通过该分界值将数组分成左右两部分
(2) 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边，此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值
(3) 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也做类似处理
(4) 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序，当左、右两个部分各数据排序完成后，整个数组的排序也就完成了
-
复杂度分析：
-
最优时间复杂度:
O(nlogn) -
最差时间复杂度:
O(n^2) -
算法稳定性：不稳定
-
原地排序：是
-
1 | def quick_sort(alist,start,end): |
4 二分查找
4.1 二分查找
-
特点
二分查找又称`折半查找`，它是一种效率较高的查找方法，①必须采用顺序存储结构 ②必须按关键字大小有序排列。 -
基本思想
将数组分为三部分，依次是中值前，中值，中值后，将要查找的值与中值进行比较，若小于中值则在中值前面找，若大于中值则在中值后面找，等于中值时直接返回。 -
复杂度分析
-
最差时间复杂度:
O(logn) -
最优时间复杂度:
O(1)
-
4.2 代码实现
4.2.1 递归版本
1 | def binary_search(alist, item): |
4.2.2 递归优化版本
1 | def binary_search_achieve(alist, item, start, end): |
4.2.3 非递归版本
1 | def binary_search(alist, item): |
4.2.4 二分查找 - 位置
1 | def binary_search_first(alist, item): |
4.2.5 第一个位置
1 | def binary_search(alist, item): |
4.2.6 最后一个位置
1 | def binary_search(alist, item): |
5 非线性数据结构 - 树
5.1 特点
一种 非线性结构 ，用来模拟具有树状结构性质的数据集合。它是由 n（n>=1）个有限节点组成一个具有层次关系的集合。
①每个节点有零个或多个子节点
②没有父节点的节点称为根节点
③每一个非根节点有且只有一个父节点
④除了根节点外，每个子节点可以分为多个不相交的子树
名字由来：因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的.
-
拓展：线性结构和非线性结构
-
线性结构：数据元素之间存在着 “一对一” 的线性关系的数据结构
-
特点
①集合中必存在唯一的一个 " 第一个元素”
②集合中必存在唯一的一个 "最后的元素"
③除最后元素之外，其它数据元素均有唯一的 "后继"
④除第一元素之外，其它数据元素均有唯一的 " 前驱”
-
-
非线性结构：一个结点元素可能对应多个直接前驱和多个后继的数据结构
-
5.2 树的术语
节点的度：一个节点含有的子树的个数称为该节点的度树的度：一棵树中，最大的节点的度称为树的度叶节点或终端节点：度为零的节点父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点兄弟节点：具有相同父节点的节点互称为兄弟节点节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推树的高度或深度：树中节点的最大层次堂兄弟节点：父节点在同一层的节点互为堂兄弟节点的祖先：从根到该节点所经分支上的所有节点子孙：以某节点为根的子树中任一节点都称为该节点的子孙森林：由 m（m>=0）棵互不相交的树的集合称为森林
5.3 树的分类
5.3.1 无序树
树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树
5.3.2 有序树
树中任意节点的子节点之间有顺序关系，这种树称为有序树
- 霍夫曼树 （用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树
- B树 ：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个的子树
1 二叉树
-
特点：每个节点最多含有两个子树的树，通常子树被称作 “左子树”（left subtree）和 “右子树”（right subtree）
-
分类
-
完全二叉树：对于一颗二叉树，假设其深度为 d (d>1)。除了第 d 层外，其它各层的节点数目均已达最大值，且第 d 层所有节点从左向右连续地紧密排列的二叉树。 -
满二叉树：所有叶节点都在最底层的完全二叉树 -
平衡二叉树（AVL 树）：当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树 -
排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）
-
-
基本要求
（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值
（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值
（3）左、右子树也分别为二叉排序树
排序二叉树包含空树
-
存储方式
顺序存储：将数据结构存储在固定的数组中，虽然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树存储方式。链式存储：由于对节点的个数无法掌握，常见树的存储表示都转换成二叉树进行处理，子节点个数最多为 2
-
应用场景
①xml，html 等，那么编写这些东西的解析器的时候，不可避免用到树
②路由协议就是使用了树的算法
③mysql 数据库索引
④文件系统的目录结构
⑤所以很多经典的 AI 算法其实都是树搜索，此外机器学习中的 decision tree 也是树结构 -
性质：
性质 1: 在二叉树的第 i 层上至多有
2^(i-1)个结点（i>0）
性质 2: 深度为 k 的二叉树至多有2^k-1个结点（k>0）
性质 3: 对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2 的结点总数为 N2，则N0=N2+1
性质 4: 最多有 n 个结点的完全二叉树的深度必为log2(n+1)
性质 5: 对完全二叉树，若从上至下、从左至右编号，则编号为 i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1, 其父节点的编号必为i//2（i＝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
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
91
92
93
94
95
96
97
98
99
100
101
102
103import queue
class Node(object):
"""节点类"""
def __init__(self, item):
# 数据类型 10
self.item = item
# Node
self.lchild = None
# Node
self.rchild = None
class BinaryTree(object):
"""二叉树"""
def __init__(self, node=None):
# Node类型 根节点
self.root = node
def add(self, item):
add_node = Node(item)
# 空二叉树
if self.root == None:
self.root = add_node
return
my_queue = queue.Queue()
# 把root放入到队列中
my_queue.put(self.root)
while True:
# 获取元素
node = my_queue.get()
# 左右节点是否为空
if node.lchild == None:
node.lchild = add_node
return
if node.rchild == None:
node.rchild = add_node
return
# 放入左右节点
my_queue.put(node.lchild)
my_queue.put(node.rchild)
def breadh_travel(self):
"""广度优先遍历"""
if not self.root:
return
# 定义队列
my_queue = queue.Queue()
# 放入根节点
my_queue.put(self.root)
while not my_queue.empty():
node = my_queue.get()
# 当前节点数据打印
print(node.item,end='')
# 左右节点添加到队列中
if node.lchild:
my_queue.put(node.lchild)
if node.rchild:
my_queue.put(node.rchild)
def preorder_travel_out(self):
self.__preorder_travel(self.root)
def __preorder_travel(self, root):
'''先序遍历: 给根节点 可以把这个节点按照根左右的方式遍历出来'''
if root:
# 根
print(root.item,end='')# 0
# 左子树
self.__preorder_travel(root.lchild)
# 右子树
self.__preorder_travel(root.rchild)
# 给一个节点 就可以对这个节点以及这个节点一下的节点进行中序遍历
def inorder_travel(self, root):
"""中序遍历 左 根 右"""
if root is not None:
self.inorder_travel(root.lchild)
print(root.item, end="")
self.inorder_travel(root.rchild)
# 给一个节点 就可以对这个节点以及这个节点一下的节点进行后序遍历
def postorder_travel(self, root):
"""后序遍历 根 左 右"""
if root is not None:
self.postorder_travel(root.lchild)
self.postorder_travel(root.rchild)
print(root.item, end="")
if __name__ == '__main__':
tree = BinaryTree()
tree.add("0")
tree.add("1")
tree.add("2")
tree.add("3")
tree.add("4")
tree.add("5")
tree.add("6")
tree.add("7")
tree.add("8")
tree.add("9")
tree.postorder_travel(tree.root) -
完全二叉树添加节点
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
77import queue
class Node(object):
"""节点类"""
def __init__(self, item):
self.item = item
self.lchild = None
self.rchild = None
class BinaryTree(object):
"""完全二叉树"""
def __init__(self, node=None):
self.root = node
def add(self, item):
"""添加节点"""
if self.root == None:
self.root = Node(item)
return
# 队列
que = queue.Queue()
# 从尾部添加数据
que.put(self.root)
while True:
# 从头部取出数据
node = que.get()
# 判断左节点是否为空
if node.lchild == None:
node.lchild = Node(item)
return
else:
que.put(node.lchild)
if node.rchild == None:
node.rchild = Node(item)
return
else:
que.put(node.rchild)
def breadh_travel(self):
"""广度优先遍历"""
if self.root == None:
return
# 队列
que = queue.Queue()
# 添加数据
que.put(self.root)
while not que.empty():
# while queue:
# 取出数据
node = que.get()
# 当前节点数据
print(node.item, end="")
# 判断左右子节点是否为空
if node.lchild is not None:
que.put(node.lchild)
if node.rchild is not None:
que.put(node.rchild)
if __name__ == '__main__':
tree = BinaryTree()
tree.add("A")
tree.add("B")
tree.add("C")
tree.add("D")
tree.add("E")
tree.add("F")
tree.add("G")
tree.add("H")
tree.add("I")
tree.breadh_travel() -
二叉树深度优先遍历
-
-
广度优先可以找到最短路径
-
深度优先往往可以很快找到搜索路径
1 | class Node(object): |
-
根据遍历结果反推二叉树
-
知道
中序遍历和先序遍历 或者 后序遍历就可以推出二叉树的结构
