一、 数据结构:基本数据结构:栈、队列、背包、优先队列
排序:排序、归并排序、堆排序、基数排序
查找:二叉查找树、红黑树、哈希表(散列表)
二、动态连通性问题
开启有效算法的流程
①建立数学问题模型
②找出解决问题的算法
③若出现问题(算法不够快,或者存储空间不足),找到问题的源头,提出新算法
④循环以上,直至满意
并查集问题
image 1
有N个对象,编号0~N-1,利用 find 判断两元素是否通过已有路径连通(union),上图中,0,1,2,5,6,7中任两元素连通,3,4,8,9任两元素连通,但是这两个集合之间元素并不是连通的。如若集合元素很多,不能很快判断元素相连情况,目前问题是:两元素间能否找到一条路径?使用高效的并查集。
image 2
1. 分析connected 性质:
①对称性(p连接到q 等价于q连接到p )
②传递性(p连接到q,q连接到r 等价于p连接到r)
2. 建立连通分量概念
image 3
性质:①连通分量中任意两对象是相连的
②连通分量中对象不与连通分量之外的对象相连
3. 命令
Find 查找 :检查两个对象是否在相同的元素中
Union 合并:将包含两个对象的分量替换为其并集
4. 编程思想Java
创建类UF,包含两个命令Find和Union,需要对象的数量
public static void main(String[] args)
{
int N = StdIn.readInt(); #读取数据
UF uf = new UF(N)
while (!StdIn.isEmpty())
{
int p = StdIn.readInt(); #客户端从输入读取两个整数
int q = StdIn.readInt();
if (!uf.connected(p,q)) #如果没有相连,则将其相连,并输出
{
uf.union(p,q);
StdOut.println(p + " " + q);
}
}
}
2019-02-03
观看普林斯顿大学数据结构课程至 2-3 快速合并 Quick-Union
- 快速查找 Quick-Find(贪心算法)
① 查找:p和q是否有相同的id,相同id代表p和q在相同的连通分量中(即连接)
② 合并:要合并两个给定对象的两个分量,要将所有与给定对象之一相同id对应的项变为另一给定对象对应的项,将所有和id[p]相同ID值的数组成员的值,全部转换为id[q] 的ID值。
image
代码,原文是Java,我改成了Python
class QuickFind:
def QuickFind(N):
id = []
for i in range(N):
id.append(i) #对每一个对象署上id,构造器
def shifou_connected(p,q):
return id[p] == id[q] #判断p和q是否连接,即两者id是否相同
def Union(p,q):
pid = id[p]
qid = id[q]
for i in range(id.length):
if (id[i == pid]):
id[i] = qid #所有和id[p]相同ID值的数组成员的值,全部转换为id[q] 的ID值
效率问题:对 N 个元素执行 N 次 union 操作,数组访问次数就是 N^2 次,当N变得很大的时候,效率会很差。下面讲到的快速合并会解决这个问题。
- 快速合并 Quick-Union
数据结构同快速查找,连通的元素按照树的结构相连,每个树都有根节点
①查找: 看p和q的根节点是否相同
②合并: 将p的根节点移到q的根节点下
image
代码,Python
class QuickUnion:
def QuickUnion(N):
id = []
for i in range(N):
id.append(i) #对每一个对象署上id
def root(i): # 根节点
while(i != id[i]):
i = id[i]
return i
def shifou_connected(p,q):
return root[p] == root[q] #判断p和q是否连接,即两者id是否相同
def Union(p,q):
i = root(p)
j = root(q)
id[i] = j # 将p的根节点移到q的根节点下
效率问题:当树很瘦长时,查找的时间会长,找一片“叶子”要回溯整棵树。花费N次时间查找(快速查找中只话1次时间),下面看改进。
-
2019-02-09
改进1:带权快速合并算法
在快速合并的基础上,对树进行加权操作。
①查找: 看p和q的根节点是否相同
②合并: 检查树的大小,将小树的根节点连接到大树的根节点上,主要做法,改变id记录值,改变数组的大小
python 代码
def shifou_connected(p,q):
return root[p] == root[q] # 判断p和q是否连接,即两者id是否相同
def Union(p,q):
i = root(p)
j = root(q)
if (i == j):
return
if (sz[i]<sz[j]):
id[i] = j # 将树小的根节点安置在树大的根节点下
sz[j] += sz[i] # 更新sz矩阵
效率问题:
任意节点深度<=log2(N)
证明:
- 只有当T2的尺寸>=T1的尺寸的时候,T1才会加到T2的根节点下,此时T1里面的x的深度才会增加。同时,T1和T2合并为一个集合,这个集合的尺寸至少是T1的2倍,在这种情况下,我们粗略估计,x的深度每增加1,则x所在集合的尺寸就会变为原来的2倍(粗略估计),但是,整个集合的元素个数为N,也就是,x所在集合的尺寸最大只能为N,从刚开始x所在集合的尺寸为1,到x所在集合的尺寸为N,需要翻倍的次数为log2(N),也就是需要翻倍log2(N)次,而假设每次翻倍深度都会增加1,所以x的深度就是log2(N)。
表1. 三种算法效率比较
image
改进2:回溯一次路径找到根节点,再回溯一次将树展平
python
def root(i): # 根节点
while(i != id[i]):
{
id[i] = id[id[i]]] # 只加这一行
i = id[i]
}
return i
image 效率
N个对象,M个查找与合并操作,需要访问数组最多c(N+Mlg(N))次,实际生活中,lg(N)可以认为是小于5的数,这种算法是很快速的。
网友评论