Дисјунктни-сет (структура података) — разлика између измена
Садржај обрисан Садржај додат
м референце |
м ispravke |
||
Ред 6:
# Пронађи: Одређује у ком се подскупу налази неки елемент. Ово може да се користи за одређивање да ли су два елемента у истом подскупу.
# Унија: Спаја два подскупа у један подскуп.
Још једна битна операција је НаправиСкуп, која прави скуп који се састоји од задајућег елемента, другачије назван
У циљу прецизније дефинисати ове операције, потребан је неки начин представљања.Један уобичајен приступ је да изаберете фиксни елемент сваког скупа,
који ће бити представник тог скупа, да представља скуп као целину. Затим, Пронађи(к) враћа представника скупа у ком се налази к,
Ред 43:
У овом наивном облику, овај приступ није ништа бољи од приступа повезаних листа, јер дрво може да буде веома неуравнотежено; међутим, може се побољшати на два начина.
Први начин који се зове унија по ранковима је да се увек мање дрво надовезује на корен већег дрвета. У контексту овог алгоритма, термин ранк се користи уместо дубине.
Дрвећа са једним елементом су дефинисана да им је ранк 0 и када год се два дрвета која имају исти ранк
Само применом ове технике најгоре време извршавања је О(лог н) за било коју од 3 наведене операције (НаправиСкуп, Унија или Пронађи).
Псеудокод:
Ред 68:
Ове две технике комплеметнирају једна другу. Прмењују се заједно време за рад је само <math>O(\alpha(n))</math>, where <math>\alpha(n)</math> is the [[inverse function|inverse of the function]] <math>n = f(x) = A(x,x)</math>, and <math>A</math> екстремно брзо расте [[Ackermann function] ]. Пошто <math>\alpha(n)</math> је обрнуто од ове функције, <math>\alpha(n)</math> је мање од 5 за све даљине практичне вредности <math>n</math>. Дакле, време извршавања по операцији је ефикасно мала константа.
У ствари, ово је [[асимптотски оптималан]] : [[Michael Fredman|Fredman]] и Saks су показали 1989. да <матх> \ омега (\ алпха (н)) </ матх> речи морају бити приступљене '' било ''ком дисјунктном-скупу структура података по операцији у просеку <ref> {{ Citation |first=M. |last=Fredman |authorlink=Michael Fredman |first2=M. |last2=Saks |title=The cell probe complexity of dynamic data structures |journal=Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing |pages=345–354 |date=May 1989 |quote=Theorem 5: Any CPROBE(log ''n'') implementation of the set union problem requires Ω(''m'' α(''m'', ''n'')) time to execute ''m'' Find's and ''n''−1 Union's, beginning with ''n'' singleton sets. }}
'''<big>Примена</big>'''
| |||