Селекциони алгоритам

У информатици, селекциони алгоритам је алгоритам који проналази k-ти најмањи елемент у повезаној листи или низу. Овај алгоритам укључује и случајеве тражења најмањег елемента и највећег елемента, као и медијане. Постоје алгоритми који су временске сложености O(n), а постоје и алгоритми сублинеарне сложености за посебне податке (екстремни случај, O(1) за сортиране податке). Селекција је подпроблем комплекснијих проблема попут тражења најближег комшије и најкраћег пута. Многи алгоритми за селекциују су изведени из алгоритама сортирања, али и неки алгоритми за сортирање се могу имплементирати понављањем процеса селекције.

Најједноставнији алгоритам за тражење k-тог елемента је тражење минимума или максимума, затим у наредним итерацијама поновно тражење минимума односно максимума преосталих чланова. У овом случају је најтеже наћи медијану, пошто је потребно поновити овај процес n/2 пута. Ипак, постоји специјални алгоритам за селекцију медијане, који се може користи за генерални алгоритам селекције. Најкоришћенији алгоритам је квикселект, који сличан алгоритму квиксортом. Попут квиксорта, асимптотски има оптималне перформансе, али у најгорем случају има лоше, што се може модификовати, тако да пруже оптималне перформансе и у најгорем сценарију.

Селекција сортирањем

Тражење k-тог елемента низа или повезане листе се може извршити тако што ће се низ или повезана листа сортирати, затим изабрати жељени елемент. Овај начин селектовања се своди на проблеме сортирања. Иако неефикасан за бирање једног елемента, овај метод може бити ефикасан уколико нам је потребно да изаберемо више елемената, тако што ћемо сортирати низ или листу у сложености O(n log n), затим у временској сложености О(1) изабрати сваки жељени елемент у низу, односно О(n) за одабир свих жељених елемената у повезаној листи. Генерално, сортирање се извршава у сложености (n log n), где је n дужина низа, али могуће је и сортирање алгоритмима који не користе поређење елемената, попут радикс сортирања и сортирања пребројавањем.

Бољи начин од сортирања целог низа или листе је парцијално сортирање највећих или најмањих k елемената. После сортирања, елементима можемо приступати у О(1) за сваки елемент у низу, или О(k), за све елементе у листи. За сортирање низа или листе на овај начин је временски потребно O(n + k log k), што је за мало k, велика уштеда у односу на сортирање целог низа.

Неуређено працијално сортирање

Уколико применимо алгоритам парцијалног сортирања за k елемената, али не поређамо елементе редом, ослобађамо се фактора O(k log k). Потом, тражење максимума у поднизу од k елемената се може урадити у O(k) времену. Како је $k\leq n$ и за овај део алгоритма ће нам асимптотски бити потребно O(n) времена.

На лак начин се могу издвојити k најмањих елемената, тако што ћемо проћи цео низ или листу, и обележити све елементе елементе који су мањи од k-тог. Такђе, овај алгоритам се извршава у O(n) времену.

Избор парцијалним сортирањем

Једноставан пример избора елемената парцијалним сортирањем је само коришћење парцијалног сортирања селекцијом

Очигледан линеарни алгоритам за тражење минимума/максимума, који се своди на пролажење кроз сваки елемент низа или листе и памћење минимума/максимума који се примењује у сортирању селекцијом, може бити оптимизован алгоритмима попут хип сорта.

Генерално, парцијално сортирање селекцијом се извршава у временској сложености O(kn). Асимптотски, овај алгоритам је неефикасан, али за мало k може бити ефикасан и једноставан је за имплементацију. Једноставно, нађемо минималан елемент и ставимо га на почетак. Ако процес поновимо k пута, k-ти елемент у низу или листу ће заиста бити k-ти елемент по величини. Алгоритам изгледа овако:

 function select(lista[1..n], k)
     for i from 1 to k
         najmanjiIndeks = i
         najmanjaVrednost = lista[i]
         for j from i+1 to n
             if lista[j] < najmanjaVrednost
                 najmanjiIndeks = j
                 najmanjaVrednost = lista[j]
         swap lista[i] and lista[najmanjiIndeks]
     return lista[k]

Одабир елемената базиран на партицији

Линеарне перформансе се могу достићи коришћењем алгоритма квикселект. Квикселект је модификација алгоритма квиксорт. У оба алгоритма се бира пивот и затим се према њему дели на партиције. Док квиксорт обрађује обе партиције, квикселект обрађује само страну где се жељени k-ти елемент налази. квикселект овом оптимизацијом има просечну сложеност O(n). За пивот се обично бира први елемент, што у највећем броју случаја даје резултате у сложености O(n). Проблем се јавља код већ сортираних низова, где се може искористити насумичан одабир пивота. Такође, постоје комбиноване методе алгоритама, који раде у просечном времену за оба случаја.

Алгоритми базирани на партицији се генерално извршавају у месту (у меморијској сложености О(1)) и својим извршавањем парцијално сортирају податке. Уколико се алгоритам не извршава у месту, потребно је обезбедити још O(n) меморијског простора.

Стратегија бирања медијане за пивот

Алгоритми за селекцију могу бити реализовани преко модификације квикселекта или квиксорта, тако што ће се за пивот увек узимати елемент чија је вредност медијана посматраног скупа. Уколико је избор пивота аимптотски оптималан (у линеарном времену), онда је и селекција и сортирање такође оптимално. У пракси се ова техника не користи, али је од теоријског значаја.

Уколико се овај алгоритам за бирање пивота искористи у алгоритму квикселект и тражење медијане буде оптимално, и сам квикселект ће се извршавати у оптималном (линеарном) времену, односно O(n). Разлог за то је чињеница да алгоритам квикселект припада групи алгоритама подели па владај, и коришћење медијане као пивота ће довести до тога да се посматрани скуп увек преполови, па ће број корака представљати геометријску прогресију.

Слично, овај приступ се може искористити у алгоритму квиксорт. Уколико изаверемо медијану за пивот у сваком кораку у оптималном времену O(n), цео алгоритам ће имати временску сложеност O(n log n). Медијана је најбољи пивот за сортирање, зато што дели скуп на подједнаке делове, и тиме гарантује оптимално сортирање, претпостављајући да је алгоритам за селекцију медијане оптималан.

Инкрементално сортирање селекцијом

Конверзија алгоритма за селекцију у алгоритам за соритрање се може урадити једноставним његовим понављањем. Сам алгоритам враћа један члан низа или листе (k-ти елемент), али у пракси алгоритам често сортира део низа (односно све пивоте пре k - тог елемента по величини.) Елементи између 2 пивота су и по вредности између њих, али не поређани редом.

Чињеница да сортирамо до нза може бити од значаја уколико радимо са истим подацима. У екстремном случају када нам је низ сортиран, елементу можемо приступити у O(1).

Код парцијално сортираних низова, уколико тражимо j-ти по реду, где је j мање или једнако k, j-том елементу можемо приступити такође у временској сложености O(1). Уколико је j веће од k, само је потребно сортирати елементе веће од k-тог.

Уколико смо елемент нашли алгоритмом квикселект и потребно нам је да после тога нађемо нови k-ти по реду, довољно је да посматрамо елементе два пивота.

Коришћење структура података за селекцију у сублинеарном времену

За неуређену листу података, минимални елемент се може наћи у линеарном времену (Ω(n)), јер се мора проћи кроз сваки елемент (у супротном бисмо га могли пропустити). Ако уредимо листу, нпр. да буде увек сортирана, онда је избор k-тог највећег елемента тривијалан, али тада уметање захтева линеарно време, као и остале операције као што је спајање две листе.

Стратегија за постизање сублинеарног времена је да се складиште подаци на организован начин користећи одговарајуће структуре података које олакшавају селекцију. Две такве структуре података су стабла и табеле учесталости.

Када се тражи само минимум (или максимум), добар приступ је коришћење хипа који налази минимални (или максимални) елемент у константном времену, док су све остале операције, укључујући уметање, О(log n) сложености или ефикасније. Уопштено говорећи, самобалансирајуће бинарно стабло претраге се може надоградити тако да омогући уметање елемента као и проналажење k-тог највећег елемента у О(log n) времену. Једноставно у сваком чвору чувамо број његових потомака и користимо ово да одредимо којим путем ћемо се даље кретати. Бројач се ефикасно може ажурирати јер додавање чвора утиче само на О(log n) његових предака, а ротације стабла утичу само на бројаче чворова који су ротирани.

Још једна једноставна стратегија је коришћење хеш табела. Када унапред знамо опсег вредности, можемо поделити тај опсег на h подинтервала и доделити им h поља. Када умећемо елемент, уписујемо га у поље које одговара интервалу у који тај елемент пада. Да бисмо пронашли минимални или максимални елемент, у табели тражимо од почетка или од краја прво непразно поље и тражимо минимални или максимални елемент у њему. Генерално, за проналажење k-тог елемента, памтимо број елемената у сваком пољу и онда претражујемо поља слева надесно сабирајући бројаче док не стигнемо до поља које садржи тражени елемент. Жељени елемент се у том пољу може пронаћи за очекивано линеарно време.

Ако изаберемо h да буде приближно √n, за улаз који је приближно равномерно распоређен, овај алгоритам може да извршава селекције у очекиваном О(√n) времену. Нажалост, ова стратегија је осетљива на груписање елемената у уске интервале, што може довести до ћелија са великим бројем елемената (груписање се може елиминисати одабиром добре хеш функције, али проналажење елемента са k-том највећом хеш вредношћу није веома корисно). Додатно, као и хеш табеле, ова структура захтева промену величине табеле како би се одржала ефикасност у случајевима када n постане много веће од h².

Доње ограничење

У књизи Уметност рачунарског програмирања (engl. The Art of Computer Programming), Доналд Кнут расправља о извесном броју доњих ограничења за број упоређивања потребних за лоцирање t најмањих унетих података неуређене лист од n елемената (користећи само упоређивања). Постоји тривијално доње ограничење од n - 1 за минимални или максимални унос. Да би се ово видело, размотримо такмичење у којем свака игра представља једно поређење. Како сваки играч, осим победника такмичења, мора изгубити једну игру пре него што сазнамо победника, имамо доњу границу од n - 1 поређења.

Прича постаје сложенија за друге индексе. Дефинишимо $W_{t}(n)$ као минимални број поређења потребних да се пронађе t најмањих вредности. Кнут упућује на рад С. С. Кислицина (engl. S. S. Kislitsyn) који показује горње ограничење ове вредности:

$W_{t}(n)\leq n-t+\sum _{n+1-t<j\leq n}\lceil {\log _{2}\,j}\rceil$ за $n\geq t$

Ова граница се постиже за t = 2, али се боља и сложенија ограничења постижу за веће вредности t.

Просторна сложеност

Лако се види да је просторна сложеност селекционог алгоритма k + О(1) (или n - k ако је k > n/2), а алгоритми у месту могу да изаберу за О(1) додатног простора. Простор за k елемената је неопходан што се лако показује: почињемо са 1,2, ..., k, затим настављамо са k + 1, k + 1, ..., k + 1, и коначно завршавамо са j копија 0, где се j креће од 0 до k - 1. У овом случају, k-ти најмањи елемент је један од 1, 2, ..., k, у зависности од броја 0, што се може закључити тек на крају. Иницијалних k елемената се морају чувати скоро до самог краја јер не можемо смањити број могућих елемената мањих од најмањих k вредности све док нам не остане мање од k елемената. Приметимо да је проналажење минимума (или максимума) тражењем текућег минимума специјалан случај када је k = 1.

Ова просторна сложеност је постигнута коришћењем прогресивног делимичног сортирања - тражење сортиране листе тренутних најмањих k елемената. Приметимо, међутим, да селекција парцијалним сортирањем, иако просторно ефикасна, има суперлинеарну временску сложеност и да временски ефикасни селекциони алгоритми базирани на партиционисању захтевају О(n) простора.

Ово просторно ограничење објашњава уску повезаност између бирања k-тог елемента и бирања (неуређених) k најмањих елемената, јер се види да ефективни одабир k-тог елемента захтева бирање најмањих k елемената као међу-корак.

Просторна сложеност може постати проблем када је k фиксни део од k, нарочито код израчунавања медијане, где је k = n/2, као и код онлајн алгоритама. Просторна сложеност се може побољшати по цену добијања делимичног одговора или тачног одговора одређене вероватноће. О овоме ће бити више речи у наставку.

Онлајн селекциони алгоритам

Онлајн селекција се може уско односити на рачунање k-тог најмањег елемента тока, у чијем случају се могу користити парцијално сортирајући алгоритми (са k + О(1) простора за тренутних k најмањих елемената), али алгоритми базирани на партицији не могу.

Алтернативно, може бити неопходно да сама селекција буде онлајн, тј. елементи могу бити изабрани из секвенцијалног улаза у тренутку посматрања и сваки избор, односно одбацивање, је неопозиво. Проблем је изабрати, под овим ограничењима, тачан елемент из улазног низа (нпр. највеће или најмање вредности) са највећом вероватноћом.

Најједноставнији пример је проблем секретара у којем се тражи максимум са највећом вероватноћом, у чијем случају је оптимална стратегија (на случајном улазу) пронаћи максимум од првих n/e елемената, и потом изабрати први елемент који је већи од тог максимума.

Језичка подршка

Веома мали број језика има уграђене функције за генералне селекције, иако већина обезбеђује функције за проналажење најмањег или највећег елемента у повезаној листи. Значајан изузетак је програмски језик C++, који обезбеђује шаблонску методу nth_element (n-ти елемент) која гарантује линеарну временску сложеност, а такође и дели улазни податак захтевајући да n-ти елемент буде сортиран на своје одговарајуће место, односно да су елементи пре n-тог елемента мањи од њега, а елементи после n-тог елемента већи од њега. Пожељно је, али не и обавезно, да подела улазног податка буде заснована на Хоровом алгоритму (или некој његовој варијацији) који има просечну линеарну временску сложеност.^[1]^[2]

C++ такође обезбеђује и nth_element (n-ти елемент) уграђену функцију^[3] која решава проблем проналажења најмањег k-тог елемента у линеарном времену, истовремено преуређујући улазни податак. Она се може искористити и за решавање проблема проналажења највећег k-тог елемента у линеарном времену, преуређујући у обрнутом поретку.

Стандардна библиотека програмског језика Пајтон (од 2.4) укључује heapq.nsmallest() и nlargest() функције које враћају сортиране листе, за O(n log k) временску сложеност.^[4]

С обзиром да је језичка подршка за сортирање све више присутна, поједностављени приступ сортирању које је праћено индексирањем је пожељно у многим окружењима упркос свом недостатку у брзини.

Референце

^ Section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E)
^ nth_element, SGI STL
^ „std::nth_element”. cppreference.com. Приступљено 20. 5. 2014.
^ python - How does heapq.nlargest work? - Stack Overflow

Литература

Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (1973). „Time bounds for selection” (PDF). Journal of Computer and System Sciences. 7 (4): 448—461. doi:10.1016/S0022-0000(73)80033-9.
Floyd, R. W.; Rivest, R. L. (1975). „Expected time bounds for selection”. Communications of the ACM. 18 (3): 165—172. doi:10.1145/360680.360691.
Kiwiel, K. C. (2005). „On Floyd and Rivest's SELECT algorithm”. Theoretical Computer Science. 347: 214—238. doi:10.1016/j.tcs.2005.06.032.
Knuth, Donald (1997). The Art of Computer Programming. Volume 3: Sorting and Searching, Third Edition. Addison-Wesley. ISBN 978-0-201-89685-5. Section 5.3.3: Minimum-Comparison Selection. стр. 207—219.
Thomas H. Cormen; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3. Chapter 9: Medians and Order Statistics. стр. 183—196. Section 14.1: Dynamic order statistics. стр. 302—308.
Paul E. Black, Select at the National Institute of Standards and Technology, Dictionary of Algorithms and Data Structures.

Спољашње везе

"Lecture notes for January 25, 1996: Selection and order statistics", ICS 161: Design and Analysis of Algorithms, David Eppstein

[1] Section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E)

[2] th_element, SGI STL

[3] „std::nth_element”. cppreference.com. Приступљено 20. 5. 2014.

[4] ython - How does heapq.nlargest work? - Stack Overflow

[1]

[2]

[3]

[4]