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

Worst case constructions for DSU?
Автор shsh, история, 12 месяцев назад, По-английски

What sequences of union/find queries will achieve the worst case complexity of a DSU? I'm specifically interested in a DSU with path compression but without union by rank/size, which has worst case complexity $$$\mathcal{O}(m \log n + n)$$$, but constructions for other variations are welcome as well.

A nice proof for the $$$\mathcal{O}(m \log n + n)$$$ bound would also be appreciated.

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

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by shsh (previous revision, new revision, compare).

→ Ответить
»
12 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +77 Проголосовать: не нравится

A binomial tree represents one of the worst cases for a DSU.

We define the binomial tree $$$T_k$$$ recursively as follows:

  • $$$T_0$$$ consists of a single vertex.
  • For $$$k\ge 1$$$, $$$T_k$$$ can be constructed by taking two copies of $$$T_{k-1}$$$ and making the root of one a child of the root of the other.
Image (Binomial Tree)

It's clear that $$$T_k$$$ has $$$2^k$$$ vertices and a depth of $$$k+1$$$.

Now, consider a DSU whose structure matches $$$T_k$$$. ($$$k=3$$$ in the following example)

If we repeatedly perform a union operation which attaches the binomial tree as a child of a single vertex, then apply a find operation starting from the deepest vertex, we observe that the resulting DSU structure is similar to $$$T_k$$$ (with an additional vertex).

Image (Union and Find)

Each find operation has a time complexity of $$$\Theta(k)=\Theta(\log n)$$$.

→ Ответить
  • »
    »
    12 месяцев назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +8 Проголосовать: не нравится

    Thanks! Do you have a nice proof for why the bound is $$$\mathcal{O}(m \log n + n)$$$? The proof here is pretty nice, but it actually shows an $$$\mathcal{O}((m + n) \log n)$$$ if I'm not mistaken since the sum of potentials initially can be $$$\mathcal{O}(n \log n)$$$.

    EDIT: Nevermind, the linked proof is actually correct since $$$m$$$ is the total number of operations, not just the number of find operations.

    → Ответить
»
11 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

its so white and all over the screen!! shsh posted :)

→ Ответить