Coursera Algorithms I Notes.1 Union Find

WQU算法的前提是，一棵树的深度永远小于自己的节点数，当然这是显而易见的：拥有一个节点的树深度为1，两个节点的树深度为2，三个节点的树深度最小为2最多为3，深度永远不可能超过节点数，因为深度是定义与层上的，没有节点就没有层，因此假如A的节点数小于B的节点数，

 Weighted Quick Union的树深度最多为lgN，N为node数量，因为WQU的Union操作时，一棵树只有在自身节点数量小于对方时，自己的根节点才会被合并到对方树的根节点上，合并之后的树至少为原来两颗树中最小的那棵树的node数量的两倍，即 Nodes of 合并之后的树=2*Min（Nodes of 树A，Nodes of 树B），因此，一颗节点数量为N的树，是若干棵树进行最多为lgN次合并（翻倍）之后产生的结果。每一次合并，节点多的那棵子树每个节点的深度不变，节点数少的那棵子树的每个节点的深度会+1，因此，对于合并之后，对于节点数量为N的一颗树来说，它的深度最多为lgN*1即lgN，在最坏的情况下。

 还有个规律可以推导出来，只有两个depth相同的树进行合并时，合并之后树的深度才会+1，其余的情况，合并之后树的深度等于合并之前拥有最大深度的树的深度。

可以用一个式子来简单表述上面这两个陈述：

if Depth of A>=Depth of B, Depth of WQU(A,B)=MAX(Depth of A, Depth of B+1);

and

2*MAX(Nodes of A, Nodes of B)>=Nodes of WQU(A,B)>=2*MIN(Nodes of A, Nodes of B).

疑问：为什么WQU算法works？为啥要以node为weight？有没有证明过程？？

我们假设DOA=DOB，因为只有此时，合并之后树的深度才会+1，不再赘述。另外我们假设WQU(A,B)=C，那么我们有：DOC=DOA|DOB+1，同时对于不同的node情况，我们对Nodes数量的变化展开以下讨论：

 假如NOA>NOB, NOC=NOA+NOB, 这是对于NOC固定的情况下，DOC最小的情况。

 假如NOA=NOB, NOC=(NOA|NOB)*2，这是对于NOC固定的情况下，DOC最大的情况，即最坏的情况，那么当这种情况不仅仅在当前AB合并时发生，而在之前每一次合并都发生时，即，不仅C是由两个Nodes数量相同的A和B合并而成，A和B也是由其他四个Nodes相同的树合并而成，那么此时的DOC为lgNOC，即lgN。

 假如NOA<NOB, 这种情况同第一种。


评论

发表评论

此博客中的热门博文

225 Implement Stack using Queues

OA: class MyStack { Queue<Integer> queue; /** Initialize your data structure here. */ public MyStack () { queue = new LinkedList<>(); } /** Push element x onto stack. */ public void push ( int x) { queue.offer(x); int k = queue.size() - 1 ; while (k > 0 ) { queue.offer(queue.poll()); k--; } } /** Removes the element on top of the stack and returns that element. */ public int pop () { return queue.poll(); } /** Get the top element. */ public int top () { return queue.peek(); } /** Returns whether the stack is empty. */ public boolean empty () { return queue.isEmpty(); } } oa是push一次就逆序排一次（相当于每次push一个之后都把新push进去的那个排到最前面，这样下次pop的时候就是pop的这一个。） ma在top和pop的时候才把最后一个调到前面来，而且每次都要重新排。（感觉其实差不多，要看这个这个stack是pop和top用得多还是push用得多） MA: class MyStack { ArrayDeque<Integer> ...
阅读全文

232. Implement Queue using Stacks

MA: class MyQueue {     Stack<Integer> simQ=new Stack<Integer>();     Stack<Integer> buffer=new Stack<Integer>();     /** Initialize your data structure here. */     public MyQueue() {     }         /** Push element x to the back of queue. */     public void push(int x) {         simQ.push(x);     }         /** Removes the element from in front of queue and returns that element. */     public int pop() {         while(!simQ.empty()){             buffer.push(simQ.pop());         }         int temp=buffer.pop();         while(!buffer.empty()){             simQ.push(buffer.pop());         }         return temp;     } ...
阅读全文

20. Valid Parentheses

OA: class Solution { public boolean isValid (String s) { char [] stack = new char [s.length()]; int head = 0 ; for ( char c : s.toCharArray()) { if (c == '(' ) { stack[head++] = c; } else if (c == '[' ) { stack[head++] = c; } else if (c == '{' ) { stack[head++] = c; } else if (c == ')' ) { if (head == 0 ) return false ; if (stack[--head] != '(' ) return false ; } else if (c == ']' ) { if (head == 0 ) return false ; if (stack[--head] != '[' ) return false ; } else if (c == '}' ) { if (head == 0 ) return false ; if (stack[--head] != '{' ) return false ; } } return head == 0 ; } } OA比MA快一倍。 String有个toCharArray()...
阅读全文