美文网首页
2019-02-23 普林斯顿大学 数据结构课程笔记

2019-02-23 普林斯顿大学 数据结构课程笔记

作者: 七月那个阿瓜呀 | 来源:发表于2019-02-23 19:28 被阅读8次

一、 数据结构:基本数据结构:栈、队列、背包、优先队列

排序:排序、归并排序、堆排序、基数排序

查找:二叉查找树、红黑树、哈希表(散列表)

二、动态连通性问题

开启有效算法的流程

①建立数学问题模型

②找出解决问题的算法

③若出现问题(算法不够快,或者存储空间不足),找到问题的源头,提出新算法

④循环以上,直至满意

并查集问题

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

  1. 快速查找 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变得很大的时候,效率会很差。下面讲到的快速合并会解决这个问题。

  1. 快速合并 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)

证明:

  1. 只有当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的数,这种算法是很快速的。

相关文章

  • 2019-01-31 数据结构

    1. 普林斯顿大学 数据结构课程笔记 -课程PPT [Coursera] Princeton算法(Part 1)笔...

  • 2019-02-23 普林斯顿大学 数据结构课程笔记

    一、 数据结构:基本数据结构:栈、队列、背包、优先队列 排序:排序、归并排序、堆排序、基数排序 查找:二叉查找树、...

  • 【BH区块链项目热点问答】普林斯顿大学正在重启比特币免费在线课程

    问:普林斯顿大学正在重启比特币免费在线课程。这对BTC算不算利好? 答:这肯定对BTC算利好呀!普林斯顿大学正在重...

  • Graph

    --------普林斯顿大学算法公开课笔记 一、Definition Graph: set of vertices...

  • Digraph

    --------普林斯顿大学算法公开课笔记 一、Digraph Directed graph,set of ver...

  • TsingHuaDSA-树

    该文章为清华大学数据结构与算法设计MOOC课程读书笔记. 1. 数据结构的静态操作与动态操作 静态操作(stati...

  • 算法

    学算法资料 电子书 《大话数据结构》(图文并茂+代码) 网站 公开课 - 普林斯顿大学 (English)http...

  • TsingHuaDSA-向量

    该文章为清华大学数据结构与算法设计MOOC课程读书笔记. 1. 抽象数据类型 VS 数据结构 2. 向量ADT 2...

  • 三、树与二叉树

    课程是中国大学MOOC浙江大学出的数据结构。作为一个数据结构爱好者,我觉得很有必要稍微整理下各章节的笔记,对知识进...

  • TsingHuaDSA-栈和队列

    该文章为清华大学数据结构与算法设计MOOC课程读书笔记. 1. 栈 1.1 接口 LIFO后进先出 1.2 栈实现...

网友评论

      本文标题:2019-02-23 普林斯顿大学 数据结构课程笔记

      本文链接:https://www.haomeiwen.com/subject/isapyqtx.html