Techniques for speeding up merging of multiple sets

  • When merging something of size X into something of size Y, it is assumed to hang O(X). python
for x in X:
    Y.add(x)
  • Repeat the merging of the elements of a set of size N into a set of size 1 with only the elements of each

    • In a naive way, O(N) merges N-1 times, so O(N^2)
    • image
  • If we decide to merge the smaller one into the larger one, this becomes O(NlogN)

    • Discussion:.
      • Let X be the smaller one.
      • Each time you merge, the size of the set will be 2X or larger.
      • If we look at an element x, it is at most times the smaller of the two.
      • image

This page is auto-translated from /nishio/小さい方から大きい方へ移す using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.