Дисјунктни-сет (структура података) — разлика између измена
Садржај обрисан Садржај додат
м ciscenje |
м Разне исправке |
||
Ред 69:
Ове две технике комплеметнирају једна другу. Прмењују се заједно време за рад је само <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
'''<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
== Историја ==
Док су идеје које су се користиле у дисјунктивним-сет шумама дуго били познате, [[Роберт Тарџан|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
До тода, најбоља граница за време по операцији, доказано од стране [[Џон Хопкрофт|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
био је доказ [[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
2007. Године Sylvain Conchon и Jean-Christophe Filliâtre су развили ''упорну структуру података'' [[persistent data structure|persistent]]
| |||