Union find data structure includes three operations. What are they? And what are their time complexities using a Linked List?
Make_set(x): O(1)
Find(x): O(1)
Union(x,y): O(n). Unless you add the shorter list to the longer one, and then X’s pointer will only get updated O(log(n)) times.
How many times can you do Union(x,y) in a data structure that holds n objects?
n-1
How many times will you need to update X’s pointer if you do n union operations?
log(n)
Because you only update X’s pointer if it is in the smaller group. You only need to update the pointer if you are joining a group that’s double X’s size. And you can only double X’s size log(n) times before you reach the size of the group - n.
What’s the total time complexity of joining two groups where you do m steps of make_set, union and find?
O(m+nlogn)
A total of m make_set and union operations which each take O(1)*m = O(m)
For any given X, its pointer will be updated at most O(logn) times. We have n X’s so in total O(nlogn)
כמה צלעות יש בעץ פורש על
N
קודקודים?
יש בדיוק
n-1
צלעות
Union find data structure includes three operations. What are they? And what are their time complexities using a Forest?
Make_set: O(1)
Find: O(n)
Union(x,y) = Union(find(x),find(y)) –> O(n^2) without adding the shorter list to the longer one.
What is Kruskal’s algorithm?
An algorithm used to find a minimum spanning tree
What are the 3 main steps in Kruskal’s algorithm?
- Initialize the data
structure (by calling Make_set(v) for every v in V) - Sort all the edges from smallest to largest.
- Pick the smallest edge and see if it forms a cycle in the spanning tree so far.
If yes - discard.
If no - add it to the tree (union)
Repeat step 3 until there are (v-1) edges in the tree.
What is the time complexity of Kruskal’s algorithm?
- Initialize the data structure by calling (Make_set(v) n times) –> O(1)*n = O(n).
- Sort the edges from smallest to largest –> O(mlogm), where m is the number of edges.
- The union and find operations take m+nlogn
Total: O(mlogm + m + nlogn)