Union-find with lists: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
Line 1: Line 1:
[[Category:Videos]]
{{#ev:youtube|https://youtu.be/wE8Y8TU-iUI|500|right|Chapters
#[00:00] Einführung
#[06:27] Wie funktioniert Union-Find nochmal?
#[07:03] Und wie war das noch mit der asymptotischen Komplexität?
|frame}}
== General information ==
== General information ==



Latest revision as of 14:27, 20 June 2015

Chapters
  1. [00:00] Einführung
  2. [06:27] Wie funktioniert Union-Find nochmal?
  3. [07:03] Und wie war das noch mit der asymptotischen Komplexität?

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.