Блог пользователя xzyxzy

How to prove the complexity of DSU that merges by size is O(logN)?
Автор xzyxzy, история, 5 лет назад, По-английски

Just like this:

int find(int x)
{
  if(f[x]==x) return x;
  return find(f[x]);
}
void merge(int x,int y)
{
  x=find(x);y=find(y);
  if(size[x]<size[y]) swap(x,y);
  f[y]=x;size[x]+=size[y];
}

I've knew that the complexity of merging by MAX-depth is $$$O(logN)$$$. But I can't figure out the proof that the complexity of merging by size is $$$O(logN)$$$. Can anyone help?

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +30 Проголосовать: не нравится

Everytime you merge a smaller component with a bigger component, it's size will at least double, so every node will be merged at most log(n) times before the size of the component it's in becomes n, which means the path between any node and the root is at most log(n)

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I have one doubt. Will the complexity will remain NlogN if I will only apply path compression and Not Apply small to large technique ?

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    Yes, but this is much harder to prove. Idea is to reduce our problem from tree to single path with HLD and then do some calculations.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Yeah. I have a little intuition that every time we iterate over some path, it's length will reduce by two. So basically each node will be at most iterated for ~ logN times.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Lets say we have a chain of nodes 1-2-...-n, with root=1 If we call find(i) then we will iterate over values j such that 1 <= j <= i. Every node=j will have as root now the node=1. Every node below i will have the same parent. Now if we call find(j) for j less than i, it will take O(1). If we call find(j) with j greater than i it will pass through i and node=i will not have children anymore, because now subtree of j with be connected with root=1. So I think that we iterate every node at most two times.

        Doesn't that mean, that we have O(n) complexity instead O(n logn) ?

        Maybe I am totally wrong, but I was curious if what I was thinking is right.

        → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

xzyxzy Refer small to large technique. DSU is using same.

→ Ответить