Дисјунктни-сет (структура података) — разлика између измена
Садржај обрисан Садржај додат
м Разне исправке |
м ispravke |
||
Ред 68:
Ове две технике комплеметнирају једна другу. Прмењују се заједно време за рад је само <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>
'''<big>Примена</big>'''
| |||