Union-find with lists: Difference between revisions
| 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 | 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
General information
Abstract Data Structure: Union-find
Implementation Invariant:
- 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".
- Each non-empty sequence in this array contains one of the partition sets, that is:
- Each element of [math]\displaystyle{ \{1,\ldots,N\} }[/math] is contained in exactly one sequence of [math]\displaystyle{ A }[/math].
- There are no other numbers in these sequences.
- 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:
- find: For input [math]\displaystyle{ i }[/math], just return the head of the sequence [math]\displaystyle{ A[S[i]] }[/math].
- 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.