ARTP - 07 - Pravdepodobnostné algoritmy. Problém výberu i-teho prvku

Zhrnutie prednášky

Prednáška sa venuje problému výberu i-teho najmenšieho prvku v poli, ktorého špeciálnym prípadom je hľadanie mediánu. Naivné riešenia s opakovaným hľadaním minima (O(i·n), pri mediáne O(n²)) alebo s triedením (O(n log n)) sa porovnávajú s cieľom dosiahnuť lineárny čas. Základom je rozdelenie poľa podľa pivota na časti menších, rovných a väčších prvkov a rekurzívne hľadanie v jednej z nich. Pri nevhodnom výbere pivota (minimum alebo maximum) je najhorší prípad O(n²). Preto sa predstavuje deterministický algoritmus Select s mediánom mediánov päťprvkových skupín, ktorý garantuje, že pivot ponechá najviac tri štvrtiny prvkov. Analýza ukazuje geometrický rad, no pivot sa hľadá rekurzívnym volaním tej istej funkcie, takže treba upraviť rekurenciu.

• - Problém: nájsť i-ty najmenší prvok poľa; medián je prípad i = n/2.
• - Naivné riešenia: opakované hľadanie minima O(i·n), pri mediáne O(n²), alebo triedenie O(n log n).
• - Rozdelenie poľa podľa pivota na less, equal a more a rekurzia len do jednej časti; pri more sa i zmenšuje o veľkosti less a equal.
• - Pivot ako prvý, posledný či stredný prvok môže viesť k najhoršiemu času O(n²).
• - Medián mediánov: n/5 skupín po piatich, medián každej skupiny a medián týchto mediánov ako pivot.
• - Takýto pivot zaručí aspoň štvrtinu prvkov menších aj väčších, takže rekurzia pokračuje na najviac 3n/4 prvkoch.
• - Rekurencia musí zahŕňať aj druhé volanie Select na nájdenie pivota (na n/5 prvkoch), nielen geometrický rad 3/4.

Zhrnutie pripravené s pomocou AI z prepisu videa.