Дисјунктни-сет (структура података) — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 1:
{{МАТФ032014}}
[[File:Dsu disjoint sets init.svg|thumb|360px|''MakeSet'' creates 8 singletons.]]
[[File:Dsu disjoint sets final.svg|thumb|360px|After some operations of ''Union'', some sets are grouped together.]]
Линија 65 ⟶ 66:
xRoot.rank := xRoot.rank + 1
Ове две технике комплеметнирају једна другу. Прмењују се заједно време за рад је само <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] ]. Пошто <
У ствари, ово је [[асимптотски оптималан]] : [[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. }} </ref>
Линија 71 ⟶ 72:
'''<big>Примена</big>'''
Примена дисјунктивног-сета структура података модела подела скупа[[Partition of a set|partitioning of a set], је на пример да пратите повезане компоненте[[Connected component (graph theory)|connected components]] неусмереног графа [[undirected graph]]. Овај модел се затим може користити за одређивање да ли две гране припадају истом чвору, или да ли ће додавање границе између њих резултирати у циклуцом. Унија-Нађи алгоритам се користи у имплементацијама високих перформанси [[Unification (computer science)|Unification]]. <ref>{{cite journal |last1=Knight |first1=Kevin|year=1989 |title=Unification: A multidisciplinary survey |journal=ACM Computing Surveys|pages=93–124 |url=http://portal.acm.org/citation.cfm?id=62030|doi=10.1145/62029.62030 |volume=21}}</ref>
== Историја ==
Док су идеје које су се користиле у дисјунктивним-сет шумама дуго били познате, [[Robert Tarjan]] је био први који је доказао горње границе (и ограничена верзију доње границе) у смислу инверзности [[Ackermann function]], 1975. <ref>{{cite journal |last1=Tarjan |first1=Robert Endre |author1-link=Robert E. Tarjan |year=1975 |title=Efficiency of a Good But Not Linear Set Union Algorithm |journal=Journal of the ACM |volume=22 |issue=2 |pages=215–225 |url=http://portal.acm.org/citation.cfm?id=321884 |doi=10.1145/321879.321884 }}</ref>
До тода, најбоља граница за време по операцији, доказано од стране [[John Hopcroft|Hopcroft]] и [[Jeffrey Ullman|Ullman]],<ref>{{cite journal |last1=Hopcroft |first1=J. E. |author1-link=John Hopcroft |last2=Ullman |first2=J. D. |author2-link=Jeffrey Ullman |year=1973 |title=Set Merging Algorithms |journal=SIAM Journal on Computing |volume=2 |issue=4 |pages=294–303 |doi=10.1137/0202024}}</ref>
био је доказ [[Proof of O(log*n) time complexity of union–find|O(log<sup>*</sup> n)]] , итеративни алгоритам од n, још једна споро растућа функција(али не спора колико и инверзна [[Ackermann function]]).
[[Robert E. Tarjan|Tarjan]] и [[Jan van Leeuwen|Van Leeuwen]] су такође развили један ''Нађи'' алгоритам који је ефикаснији у пракси али задржава нагору комплексност.<ref>{{Citation |first=Robert E. |last=Tarjan |author1-link=Robert E. Tarjan |first2=Jan |last2=van Leeuwen |author2-link=Jan van Leeuwen |title=Worst-case analysis of set union algorithms |journal=Journal of the ACM |volume=31 |issue=2 |pages=245–281 |year=1984 |doi= }}</ref>
2007. Године Sylvain Conchon и Jean-Christophe Filliâtre су развили ''упорну структуру података'' [[persistent data structure|persistent]]
верзија структуре података дисјунктних-сет шума, омогућавајући претходну верзију структуре да се ефикасно задрже, формализовају његову исправност користећи доказ [[[proof assistant]] [[Coq]].<ref>{{Citation |first=Sylvain |last=Conchon |first2=Jean-Christophe |last2=Filliâtre |contribution=A Persistent Union-Find Data Structure |title=ACM SIGPLAN Workshop on ML |location=Freiburg, Germany |date=October 2007}}</ref>
== Повезани линкови ==
* [http://www.boost.org/libs/disjoint_sets/disjoint_sets.html C++ implementation], part of the [[Boost C++ libraries]]
* [http://www.lix.polytechnique.fr/~nielsen/Srmjava.java A Java implementation with an application to color image segmentation, Statistical Region Merging (SRM), IEEE Trans. Pattern Anal. Mach. Intell. 26(11): 1452–1458 (2004)]
* [http://www.cs.unm.edu/~rlpm/499/uf.html Java applet: A Graphical Union–Find Implementation], by Rory L. P. McGuire
* ''[http://citeseer.ist.psu.edu/anderson94waitfree.html Wait-free Parallel Algorithms for the Union–Find Problem]'', a 1994 paper by Richard J. Anderson and Heather Woll describing a parallelized version of Union–Find that never needs to block
* [http://code.activestate.com/recipes/215912-union-find-data-structure/ Python implementation]
* [http://www.mathblog.dk/disjoint-set-data-structure/ Visual explanation and C# code]
== Референце ==
{{reflist|30em}}
[[Категорија:]]
| |||