Дисјунктни-сет (структура података) — разлика између измена
Садржај обрисан Садржај додат
м ispravljanje veza ka Commonsu |
м datumi |
||
Ред 67:
Ове две технике комплеметнирају једна другу. Прмењују се заједно време за рад је само <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 | 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. |pages=345-354}}</ref>
'''<big>Примена</big>'''
Ред 82:
2007. Године Sylvain Conchon и Jean-Christophe Filliâtre су развили ''упорну структуру података'' [[persistent data structure|persistent]]
верзија структуре података дисјунктних-сет шума, омогућавајући претходну верзију структуре да се ефикасно задрже, формализовају његову исправност користећи доказ [[proof assistant]] [[Coq]].<ref>{{Citation |last=Conchon|first=Sylvain|first2=Jean-Christophe |last2=Filliâtre|contribution=A Persistent Union-Find Data Structure |title=ACM SIGPLAN Workshop on ML |location=Freiburg, Germany | date = 10. 2007}}</ref>
== Референце ==
| |||