理论建构

算法复杂度分析

算法复杂度有时间和空间两种，每种都可用大OO，大Θ\Theta ，大Ω\Omega，小oo，小ω\omega 进行表示

大O表示法

大O表示法是我们在分析算法复杂度时最常用的一种表示法。

大O表示法全称为只可以表示函数运行时间和占据空间的上限，即用于描述算法的最坏复杂度。

关于大O表示法的更详细解读，参考这篇博客：图解大 O 表示法

大Ω\Omega表示法

当函数的大小只有下界，没有明确的上界的时候，可以使用大Ω表示法，该渐进描述符一般用与描述算法的 最优复杂度 。

大Θ\Theta表示法

如果一个函数 f(N)f(N) 既是 O(g(N))O(g(N)) 也是 Ω(g(N))\Omega(g(N))，则我们称 f(N)f(N) 为 Θ(g(N))\Theta(g(N))

Union-Find算法

算法API图解

QuickFind策略

对union操作的时间复杂度为O(N)O(N)

JAVA
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class UnionFindQuickFind {
    private int[] id;
    private int count;

    public UnionFindQuickFind(int N) { // 初始化分量id数组
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }

    public int count() {
        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) {
        // 将p和q归并到相同的分量中
        int pID = find(p);
        int qID = find(q);
        // 如果p和q已经在相同的分量之中则不需要采取任何行动
        if (pID == qID) return;
        // 将p的分量重命名为q的名称
        for (int i = 0; i < id.length; i++)
            if (id[i] == pID) id[i] = qID;
        count--;
    }
}

QuickUnion策略

对find的时间复杂度是O(N)O(N)，在多数情况下，quick-union方法比quick-find方法更快（最坏的情况下，quick-union在find上消耗的时间和quick-find在union上消耗的时间相当）

JAVA
private int find(int p)
{ // 找出分量的名称
    while (p != id[p]) p = id[p];
    return p;
}
public void union(int p, int q)
{ // 将p和q的根节点统一
    int pRoot = find(p);
    int qRoot = find(q);
    if (pRoot == qRoot) return;
    id[pRoot] = qRoot;
    count--;
}

改进：加权quick-union方法 该方法下find和union的时间复杂度均为O(lg⁡N)O(\lg{N})

JAVA
public class WeightedQuickUnionUnionFind {
    private int[] id; // 父链接数组（由触点索引）
    private int[] sz; // （由触点索引的）各个根节点所对应的分量的大小
    private int count; // 连通分量的数量

    public WeightedQuickUnionUnionFind(int N) {
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
        sz = new int[N];
        for (int i = 0; i < N; i++) sz[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 i = find(p);
        int j = find(q);
        if (i == j) return;
        // 将小树的根节点连接到大树的根节点
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        }
        else {
            id[j] = i;
            sz[i] += sz[j];
        }
        count--;
    }
}

路径压缩的quick-union算法： 为find()添加一个循环，将在路径上遇到的所有节点都直接连接到根节点，以得到几乎完全扁平化的树

Powered By Valine
v1.5.1