Union-find with lists: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 24: Line 24:


'''Proof:''' Obviously, a single call to the find method requires constant time. So, the contribution of all find operations is in <math>\mathcal{O}(F)</math>. On the other hand, the contribution of the constructor to the total asymptotic complexity is in <math>\mathcal{O}(N)</math>. So consider the calls to the unite method.  
'''Proof:''' Obviously, a single call to the find method requires constant time. So, the contribution of all find operations is in <math>\mathcal{O}(F)</math>. On the other hand, the contribution of the constructor to the total asymptotic complexity is in <math>\mathcal{O}(N)</math>. So consider the calls to the unite method.  
The crucial observation is that each <math>i\in\{1,\ldots,N\}</math> is moved at most <math>\mathcal{O}(\log N)</math> times. in total Why: Since always the shorter sequence is moved, the length of the sequence to which <math>i</math> belongs is at least doubled in each step in which <math>i</math> is moved. This proves the theorem.
The crucial observation is that each <math>i\in\{1,\ldots,N\}</math> is moved at most <math>\mathcal{O}(\log N)</math> times in total because: Since always the shorter sequence is moved, the length of the sequence to which <math>i</math> belongs is at least doubled in each step in which <math>i</math> is moved. This proves the theorem.

Revision as of 13:48, 20 June 2015

http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/Union-find_with_lists.html

General information

Abstract Data Structure: Union-find

Implementation Invariant:

  1. There is an array [math]\displaystyle{ A }[/math] with index range [math]\displaystyle{ \{1,\ldots,N\} }[/math] and component type "ordered sequence of integral numbers".
  2. Each non-empty sequence in this array contains one of the partition sets, that is:
    1. Each element of [math]\displaystyle{ \{1,\ldots,N\} }[/math] is contained in exactly one sequence of [math]\displaystyle{ A }[/math].
    2. There are no other numbers in these sequences.
  3. There is an array [math]\displaystyle{ S }[/math] with index range [math]\displaystyle{ \{1,\ldots,N\} }[/math] and component type [math]\displaystyle{ N }[/math]. For [math]\displaystyle{ i\in\{1,\ldots,N\} }[/math], [math]\displaystyle{ i }[/math] is in the sequence [math]\displaystyle{ A[S[i]] }[/math].

For a non-empty sequence in , the head of this sequence is the representative of the corresponding partition set.

Methods

The find and unite methods are quite simple and need no separate wiki pages:

  1. find: For input [math]\displaystyle{ i }[/math], just return the head of the sequence [math]\displaystyle{ A[S[i]] }[/math].
  2. unite: Append one sequence at the tail of the other one and clear the original position of the former sequence in [math]\displaystyle{ A }[/math]. The values [math]\displaystyle{ S[i] }[/math] of the appended elements [math]\displaystyle{ i }[/math] have to be updated according to item 3 of the implementation invariant.

Asymptotic complexity

Statement: If always the shorter sequence is appended to the longer sequence (ties arbitrarily broken), the asymptotic complexity is [math]\displaystyle{ \mathcal{O}(F+N\log N) }[/math] in the worst case, where [math]\displaystyle{ F }[/math] is the number of calls to the find method.

Proof: Obviously, a single call to the find method requires constant time. So, the contribution of all find operations is in [math]\displaystyle{ \mathcal{O}(F) }[/math]. On the other hand, the contribution of the constructor to the total asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(N) }[/math]. So consider the calls to the unite method. The crucial observation is that each [math]\displaystyle{ i\in\{1,\ldots,N\} }[/math] is moved at most [math]\displaystyle{ \mathcal{O}(\log N) }[/math] times in total because: Since always the shorter sequence is moved, the length of the sequence to which [math]\displaystyle{ i }[/math] belongs is at least doubled in each step in which [math]\displaystyle{ i }[/math] is moved. This proves the theorem.