Селекциони алгоритам — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
мНема описа измене |
||
Ред 62:
Када се тражи само минимум (или максимум), добар приступ је коришћење [[Хип (структура података)|хипа]] који налази минимални (или максимални) елемент у константном времену, док су све остале операције, укључујући уметање, О(log ''n'') сложености или ефикасније. Уопштено говорећи, самобалансирајуће бинарно стабло претраге се може надоградити тако да омогући уметање елемента као и проналажење ''k''-тог највећег елемента у О(log ''n'') времену. Једноставно у сваком чвору чувамо број његових потомака и користимо ово да одредимо којим путем ћемо се даље кретати. Бројач се ефикасно може ажурирати јер додавање чвора утиче само на О(log ''n'') његових предака, а ротације стабла утичу само на бројаче чворова који су ротирани.
Још једна једноставна стратегија је коришћење [[хеш табела]]. Када унапред знамо опсег вредности, можемо поделити тај опсег на ''h'' подинтервала и доделити им ''h'' поља. Када умећемо елемент, уписујемо га у поље
Ако изаберемо ''h'' да буде приближно {{sqrt|''n''}}, за улаз који је приближно равномерно распоређен, овај алгоритам може да извршава селекције у очекиваном О({{sqrt|''n''}}) времену. Нажалост, ова стратегија је осетљива на груписање елемената у уске интервале, што може довести до ћелија са великим бројем елемената (груписање се може елиминисати одабиром добре хеш функције, али проналажење елемента са ''k''-том највећом хеш вредношћу није веома корисно). Додатно, као и хеш табеле, ова структура захтева промену величине табеле како би се одржала ефикасност у случајевима када ''n'' постане много веће од ''h''<sup>2</sup>.
| |||