Find & Union

Powrót do listy wątków

Jak, Waszym zdaniem, powinno się to implementować, żeby się stosunkowo mało przy tym narobić oraz czas działania poszczególnych operacji był jak najlepszy ? Paweł Maśluch, 2015-06-28 12:26:59
.

Kod źródłowy:
int FInd(int a)
{
   if (p[a] != a) p[a] = Find(p[a]);
   return p[a];
}

void Union(int a, int b)
{
  p[FInd(a)] = Find(b);
}
Tomasz Ponitka, 2015-06-28 13:39:37
Czy p[a] oznacza reprezentanta zbioru, w którym jest element a ? Paweł Maśluch, 2015-06-29 08:34:38
Jak szacować czas działania tych funkcji (rozumiem, że w tym przypadku będziemy myśleć o koszcie zamortyzowanym) ? Paweł Maśluch, 2015-06-29 08:45:33
Jak myślicie, jak najłatwiej można by zaimplementować operację połączenia 2 zbiorów w 1 większy (chyba lepiej mniejszy zbiór do większego "wrzucać") ? Paweł Maśluch, 2015-06-30 20:01:12
Czy p[a] oznacza reprezentanta zbioru, w którym jest element a ? -> TAK

Jak szacować czas działania tych funkcji (rozumiem, że w tym przypadku będziemy myśleć o koszcie zamortyzowanym) ? -> "Analiza tej struktury jest bardzo trudna. Można dowieść, że n operacji union, find działają w czasie zamortyzowany O(n log*(n)), czyli prawie liniowym (nie do odróżnienia na dzisiejszych komputerach). Wygląda na to, że pojedyncze operacje union, find, działają prawie zawsze w czasie stałym. Super, co nie?" (http://rafalnowak.pl/wiki/index.php?title=UNION_FIND)

Jak myślicie, jak najłatwiej można by zaimplementować operację połączenia 2 zbiorów w 1 większy (chyba lepiej mniejszy zbiór do większego "wrzucać") ? -> łączenie dwóch zbiorów - Union(a,b) w moim kodzie; na stronie http://rafalnowak.pl/wiki/index.php?title=UNION_FIND jest implementacja wrzucająca mniejsze zbiory do większych Tomasz Ponitka, 2015-07-04 22:50:39