Big-O Notation 细节分析 局限性 对比 Important: Big O does not mean “worst case”! Often abused to mean this. 大O记号的用处 Big-Omega Notation $\Omega(f(n))$ 大Ω记号的用处 非严格证明和严格证明

不相交集问题 1 2 3 4 5 6 7 public interface DisjointSets { /** Connects two items P and Q. */ void connect(int p, int q); /** Checks to see if two items are connected. */ boolean isConnected(int p, int q); } naive implementation 真的链接两个元素，然后考虑遍历整个集合，判断是否有两个元素是连通的。 better implementation Better approach: Model connectedness in terms of sets. How things are connected isn’t something we need to know.😉 quick-find 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public class QuickFindDS implements DisjointSets { private int[] id; // really fast public boolean isConnected(int p, int q) { return id[p] == id[q]; } public void connect(int p, int q) { int pid = id[p]; int qid = id[q]; for (int i = 0; i < id.

没有捷径，全靠仔细 for loops recursion 形如$\Theta(n^k)$, $k$ 是递归的深度 binary search 形如$\Theta(\log n)$ C(N) = ⌊log2(N)⌋+1 merge sort 形如$\Theta(n\log n)$