首页 > 代码库 > 算法（Algorithms）第4版 练习 1.5.3

算法（Algorithms）第4版 练习 1.5.3

2024-09-09 01:13:14   215人阅读

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
9 1 2 3 4 5 6 7 8 9 
1 1 1 1 1 1 1 1 1 2 
9 components
3 4
9 1 2 3 3 5 6 7 8 9 
1 1 1 2 1 1 1 1 1 2 
8 components
5 8
9 1 2 3 3 5 6 7 5 9 
1 1 1 2 1 2 1 1 1 2 
7 components
7 2
9 1 7 3 3 5 6 7 5 9 
1 1 1 2 1 2 1 2 1 2 
6 components
2 1
9 7 7 3 3 5 6 7 5 9 
1 1 1 2 1 2 1 3 1 2 
5 components
5 7
9 7 7 3 3 7 6 7 5 9 
1 1 1 2 1 2 1 5 1 2 
4 components
0 3
9 7 7 9 3 7 6 7 5 9 
1 1 1 2 1 2 1 5 1 4 
3 components
4 2
9 7 7 9 3 7 6 7 5 7 
1 1 1 2 1 2 1 9 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 + 1，总的为2 * 1　　+ 2 * 1 + 1

3 4：3和4的深度都为0，find访问数组次数为1，connected为2 * 1， union为2 * 1 + 1，总的为2 * 1　　+ 2 * 1 + 1

5 8：5和8的深度都为0，find访问数组次数为1，connected为2 * 1， union为2 * 1 + 1，总的为2 * 1　　+ 2 * 1 + 1

7 2：7和2的深度都为0，find访问数组次数为1，connected为2 * 1， union为2 * 1 + 1，总的为2 * 1　　+ 2 * 1 + 1

2 1：2的深度为1，1的深度为0。find访问数组次数分别为3、1，connected为3 + 1， union为3 + 1 + 1，总的为3 + 1　　+3 + 1 + 1

5 7：5的深度为0，7的深度为0。find访问数组次数分别为1、1，connected为1 + 1， union为1 + 1 + 1，总的为1 + 1　　+1 + 1 + 1

0 3：0的深度为1，3的深度为0。find访问数组次数分别为3、1，connected为3 + 1， union为3 + 1 + 1，总的为3 + 1　　+3 + 1 + 1

4 2：4的深度为2，2的深度为1。find访问数组次数分别为5、3，connected为5 + 3， union为5 + 3 + 1，总的为5 + 3　　+5 + 3 + 1

算法（Algorithms）第4版 练习 1.5.3


联系
我们