アルゴリズム:集計(4つの方法)

3775 ワード

  • 単純および調査セット
  • public class UnionFind {
        private int[] id;
        private int count;
    
        public UnionFind(int N) {
            count = N;
            id = new int[N];
            for(int i = 0; i < N; i++) id[i] = i;
        }
    
        public int getCount() {
            return count;
        }
    
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
    
        public int find(int p) {
            return id[p];
        }
    
        public void union(int p, int q){
            int pRoot = find(p);
            int qRoot = find(q);
    
            if(pRoot == qRoot) return;
    
            for(int i = 0; i < id.length; i++)
                if(id[i] == pRoot)  id[i] = qRoot;
            count--;
        }
    }
    
  • クイックおよび調査セット
  • public class QuickUnion {
        private int[] id;
        private int count;
    
        public QuickUnion(int N) {
            count = N;
            id = new int[N];
            for(int i = 0; i < N; i++) id[i] = i;
        }
    
        public int getCount() {
            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;
    
            id[pRoot] = qRoot;
            count--;
        }
    }
    
  • 重み付け高速および調査セット
  • public class WeightedQuickUnion {
        private int[] id;
        private int count;
        private int[] sz;
    
        public WeightedQuickUnion(int N) {
            count = N;
            id = new int[N];
            sz = new int[N];
            for(int i = 0; i < N; i++) {
                id[i] = i;
                sz[i] = 1;
            }
        }
    
        public int getCount() {
            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;
    
            if(sz[pRoot] < sz[qRoot]) { id[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; }
            else                      { id[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; }
            count--;
        }
    
    
  • パス圧縮の重み付け高速およびルックアップ
  • public class PathCompressionWeightedQuickUnion {
        private int[] id;
        private int count;
        private int[] sz;
    
        public PathCompressionWeightedQuickUnion(int N) {
            count = N;
            id = new int[N];
            sz = new int[N];
            for(int i = 0; i < N; i++) {
                id[i] = i;
                sz[i] = 1;
            }
        }
    
        public int getCount() {
            return count;
        }
    
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
    
        public int find(int p) {
            if (p != id[p]) id[p] = find(id[p]);
            return id[p];
        }
    
        public void union(int p, int q){
            int pRoot = find(p);
            int qRoot = find(q);
    
            if(pRoot == qRoot) return;
    
            if(sz[pRoot] < sz[qRoot]) { id[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; }
            else                      { id[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; }
            count--;
        }
    }
    
  • 複雑度比較
  •                                              N        (    )
                                                   union()         find()
    	
    union-find                           O(n)          O(n)            O(1) 
    quick-union                          O(n)                          
      quick-union                       O(n)         O(lgn)          O(lgn)
           quick-union              O(n)             O(1)         O(1)
                                        O(n)          O(1)            O(1)