Дисјунктни-сет (структура података) — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 26:
'''function''' ''MakeSet''(x)
x.parent := x
'''function''' ''Find''(x)
if x.parent == x
return x
else
return ''Find''(x.parent)
'''function''' ''Union''(x, y)
xRoot := ''Find''(x)
yRoot := ''Find''(y)
xRoot.parent := yRoot
У овом наивном облику, овај приступ није ништа бољи од приступа повезаних листа, јер дрво може да буде веома неуравнотеженo; међутим, може се побољшати на два начина.
Ред 46:
Псеудокод:
'''function''' ''MakeSet''(x)
x.parent := x
x.rank := 0
'''function''' ''Union''(x, y)
xRoot := ''Find''(x)
yRoot := ''Find''(y)
if xRoot == yRoot
return
<u>// x and y are not already in same set. Merge them.</u>
if xRoot.rank < yRoot.rank
xRoot.parent := yRoot
else if xRoot.rank > yRoot.rank
yRoot.parent := xRoot
else
yRoot.parent := xRoot
xRoot.rank := xRoot.rank + 1
Ове две технике комплеметнирају једна другу. Прмењују се заједно време за рад је само <матх> О (\ алпха (н)) </ матх>, где <матх> \ алпха (н) </ матх> је [[инверзна функција | инверзна функцији]] <матх> н = ф (к) = (к, к) </ матх>, а <матх> А </ матх> екстремно брзо расте [[Ackermann function] ]. Пошто <матх> \ алпха (н) </ матх> је обрнуто од ове функције, <матх> \ алпха (н) </ матх> је мање од 5 за све даљине практичне вредности <матх> н </ матх> . Дакле, време извршавања по операцији је ефикасно мала константа.
У ствари, ово је [[асимптотски оптималан]]: [[Michael Fredman|Fredman]] и Сакс су показали 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. }} </ ref>
'''<big>Примена</big>'''
| |||