Википедија

Дисјунктни-сет (структура података) — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Нема описа измене
Autobot (разговор | доприноси)
1.572.075 измена
м Разне исправке; козметичке измене
Ред 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.]]
Дисјунктни-сет jeје структура података која прати скуп елемената подељена у велики број дисјунктних(непреклапајућих) подскупова.
Алгоритам за проналажење скупова је алгоритам који обавља две корисне операције на такве структуре података:
# Пронађи: Одређује у ком се подскупу налази неки елемент. Ово може да се користи за одређивање да ли су два елемента у истом подскупу.
# Унија: Спаја два подскупа у један подскуп.
Још једна битна операција је НаправиСкуп, која прави скуп који се састоји од задајућег елемента, другачије назван "синглтон".
У циљу прецизније дефинисати ове операције, потребан је неки начин представљања.Један уобичајен приступ је да изаберете фиксни елемент сваког скупа,
који ће бити представник тог скупа, да представља скуп као целину. Затим, Пронађи(к) враћа представника скупа у ком се налази к,
а Унија узима представнике два скупа као своје аргументе.
 
'''<big>Дисјунктни-сет у повезаним листама</big>'''
 
Једноставан приступ креирању Дисјунктни-сет структури је да се створи повезанaповезана листaлиста за сваки скуп. Елемент на челу сваке листе је изабран
за свог представника. НаправиСкуп креира листу једног елемента. Унија спаја две листе. Недостатак овога је да је операција Пронађи захтева линеарно време,
пролази листу уназад од датог елемента на врху листе. Ово се може избећи, укључујући у сваком чвору повезане листе показивач на почетак (чело) листе.
Онда је операцији Пронађи потребно константно време, јер овај показивач показује директно на представника скупа. Међутим, Унија сада мора да ажурира
сваки елемент у листи и сада је њој потребно линеарно време.
 
Ред 41:
xRoot.parent := yRoot
 
У овом наивном облику, овај приступ није ништа бољи од приступа повезаних листа, јер дрво може да буде веома неуравнотеженoнеуравнотежено; међутим, може се побољшати на два начина.
Први начин који се зове унија по ранковима је да се увек мање дрво надовезује на корен већег дрвета. У контексту овог алгоритма, термин ранк се користи уместо дубине.
Дрвећа са једним елементом су дефинисана да им је ранк 0 и када год се два дрвета која имају исти ранк "р" споје, резултат ранка је "р+1".
Само применом ове технике најгоре време извршавања је О(лог н) за било коју од 3 наведене операције (НаправиСкуп, Унија или Пронађи).
Ред 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] ]. Пошто <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&ndash;354 |date=May 1989 |quote=Theorem 5: Any CPROBE(log ''n'') implementation of the set union problem requires &Omega;(''m'' &alpha;(''m'', ''n'')) time to execute ''m'' Find's and ''n''&minus;1 Union's, beginning with ''n'' singleton sets. }} </ref>
Ред 78:
Док су идеје које су се користиле у дисјунктивним-сет шумама дуго били познате, [[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&ndash;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&ndash;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>
 
== Повезани линкови ==
Преузето из „https://sr.wikipedia.org/wiki/Дисјунктни-сет_(структура_података)”