算法（Algorithms）第4版 练习 1.5.3
id数组和treesize数组变化情况：
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1
10 components
9 0
1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1
9 components
3 4
9 1 2 3 5 6 7 8 9
1 1 1 1 1 1 1 1 2
8 components
5 8
9 1 2 3 3 5 6 7 9
1 1 1 2 1 1 1 1 2
7 components
7 2
9 1 3 3 5 6 7 5 9
1 1 1 2 1 2 1 1 2
6 components
2 1
9 7 3 3 5 6 7 5 9
1 1 1 2 1 2 1 1 2
5 components
5 7
9 7 7 3 3 6 7 5 9
1 1 1 2 1 2 1 1 2
4 components
0 3
9 7 7 3 7 6 7 5 9
1 1 1 2 1 2 1 5 1
3 components
4 2
9 7 7 9 3 7 6 7 5
1 1 1 2 1 2 1 1 4
2 components
森林图：
操作次数分析：
find函数每次访问数组次数是1 + 2 * depth
connected函数每次调用两次find函数
union函数每次调用两次find函数（如果两个连接点不在同一个树的话，则多一次数组访问）
public static void main(String[] args) {
//initialize N components
int N = StdIn.readInt();
UFWeightedQuickUnion uf = new UFWeightedQuickUnion(N);
StdOut.println(uf);
while(!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if(uf.connected(p, q)) {//ignore if connected
StdOut.println(p + " " + q + " is connected");
continue;
}
uf.union(p, q);//connect p and q
StdOut.println(p + " " + q);
StdOut.println(uf);
}
}
对于这个client，对每个数据对，都调用一次connected函数和union函数。
下边对数组访问次数进行分析：
9 0：9和0的深度都为0，find访问数组次数为1，connected为2 * 1， union为2 * 1 + 5，总的为2 * 1 + 2 * 1 + 5
3 4：3和4的深度都为0，find访问数组次数为1，connected为2 * 1， union为2 * 1 + 5，总的为2 * 1 + 2 * 1 + 5
5 8：5和8的深度都为0，find访问数组次数为1，connected为2 * 1， union为2 * 1 + 5，总的为2 * 1 + 2 * 1 + 5
7 2：7和2的深度都为0，find访问数组次数为1，connected为2 * 1， union为2 * 1 + 5，总的为2 * 1 + 2 * 1 + 5
2 1：2的深度为1，1的深度为0。find访问数组次数分别为3、1，connected为3 + 1， union为3 + 1 + 5，总的为3 + 1 +3 + 1 + 5
5 7：5的深度为0，7的深度为0。find访问数组次数分别为1、1，connected为1 + 1， union为1 + 1 + 5，总的为1 + 1 +1 + 1 + 5
0 3：0的深度为1，3的深度为0。find访问数组次数分别为3、1，connected为3 + 1， union为3 + 1 + 5，总的为3 + 1 +3 + 1 + 5
4 2：4的深度为2，2的深度为1。find访问数组次数分别为5、3，connected为5 + 3， union为5 + 3 + 5，总的为5 + 3 +5 + 3 + 5
源代码：
package com.qiusongde; import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class UFWeightedQuickUnion { private int[] id;//parent link(site indexed)
private int[] treesize;//size of component for roots(site indexed)
private int count;//number of components public UFWeightedQuickUnion(int N) { count = N; id = new int[N];
for(int i = 0; i < N; i++)
id[i] = i; treesize = new int[N];
for(int i = 0; i < N; i++)
treesize[i] = 1; } public int count() {
return count;
} public boolean connected(int p, int q) {
return find(p) == find(q);
} public int find(int p) { while(p != id[p])
p = id[p]; return p; } public void union(int p, int q) { int pRoot = find(p);
int qRoot = find(q); if(pRoot == qRoot)
return; //make smaller root point to larger one
if(treesize[pRoot] < treesize[qRoot]) {
id[pRoot] = qRoot;
treesize[qRoot] += treesize[pRoot];
} else {
id[qRoot] = pRoot;
treesize[pRoot] += treesize[qRoot];
} count--; } @Override
public String toString() {
String s = ""; for(int i = 0; i < id.length; i++) {
s += id[i] + " ";
}
s += "\n"; for(int i = 0; i < treesize.length; i++) {
s += treesize[i] + " ";
}
s += "\n" + count + " components"; return s;
} public static void main(String[] args) { //initialize N components
int N = StdIn.readInt();
UFWeightedQuickUnion uf = new UFWeightedQuickUnion(N);
StdOut.println(uf); while(!StdIn.isEmpty()) { int p = StdIn.readInt();
int q = StdIn.readInt(); if(uf.connected(p, q)) {//ignore if connected
StdOut.println(p + " " + q + " is connected");
continue;
} uf.union(p, q);//connect p and q
StdOut.println(p + " " + q);
StdOut.println(uf);
} } }
最新文章
- 前台处理json字符串的几种方法（转）
- GIS 网站参考
- 基于 jQuery 实现垂直滑动的手风琴效果
- 《深入理解bootstrap》读书笔记：第三章 CSS布局
- 纯window下VMware 安装 OS X El Capitan 原版映像【未完待续】
- elasticsearch插件之一：marvel
- php 通过PATH_SEPARATOR判断当前服务器系统类型
- [UML]UML之开篇
- 二维卷积c代码
- selenium webdriver(5)---超时设置
- 一键安装IIS的点点滴滴——For所有Microsoft的操作系统（下）
- 读取sd卡下图片，由图片路径转换为bitmap
- WinDBG调试.NET程序示例
- scala写算法-从后缀表达式构造
- vue项目基本流程
- CART决策树和随机森林
- 纯 CSS 绘制三角形（各种角度）
- POJ 2409 Let it Bead（polya裸题）
- 8.20 前端 js
- 2017年人工智能相关会议论文阅读笔记 （已添加ISSCC17，慢慢补充中）