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

WHAT IS THE WORST CASE OF (DSU) WHEN I USE PATH COMPRESSION ONLY
Автор mostafaabdelaal_03, история, 9 месяцев назад, По-английски 
int n;
vector<int>p, v;
int get(int a){
    return p[a] = (a==p[a]) ? a : get(p[a]);   
}
void unin(int a, int b){
    a = get(a);
    b = get(b);
    p[a] = b;
}

I implemented  this code when I was solving problems about Dsu in section Edu..now if I used path compression in get function but I donot Consider the samllest set and larget set in union ..can the comlexity reach O(N)
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

The worst case for a single function call can be $$$O(n)$$$, but the time complexity per function call is amortized $$$O(\log n)$$$, i.e. $$$q$$$ function calls will run in $$$O(q \log n)$$$ total time.

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

https://stackoverflow.com/questions/56229760/what-is-the-complexity-of-path-compression-technique-for-disjoint-set-algorithm

→ Ответить
»
9 месяцев назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Please google it, it's $$$\mathcal{O}(\log{}n)$$$ as can be read in cp algorithms website the more queries u use it'll be decreased, worst case will always be n but this will happen only once, after that it'll be n/2 then n/4 so for Q queries, you'll have $$$\mathcal{O}(Q\log{}n)$$$ (harmonic series)

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

    CP algorithms says:

    This simple modification of the operation already achieves the time complexity $$$O(\log n)$$$ per call on average (here without proof).

    you can see, cp-algo doesn't proof the time complexity of the path compression-only approach, and its proof is not that easy as you think. btw you can read "Tarjan-van Leeuwen (1984)" paper for complete proof (I also had this question one day and after searching I found this paper).

    → Ответить