Deadline: 2022-04-28 10:30 (252 days ago)
Pavel Veselý — 2022-04-14 22:32 (265 days ago) — reply
Máme dáno přirozené číslo $k\ge 1$ a poté na vstupu přicházejí čísla. Kdykoliv přijde další, vypište medián z posledních $k$ čísel (medián je $\lceil k/2\rceil$-tý nejmenší prvek). Dosáhněte časové složitosti $O(\log k)$ na operaci. Kolik je potřeba paměti, když se nepočítá vstup? (Detaily: pro prvních $k-1$ čísel není potřeba vypsat nic.) Poznámka: V této úloze můžeme na vstup nahlédnout jako na nekonečný proud dat (čísel), z nichž nás zajímá jen posledních $k$ čísel, které přišly. Tento model je studován v rámci tzv. streaming algoritmů, které jsou paměťově efektivní. Tuto úlohu lze vyřešit i s pamětí $O(\log k)$, pokud nám stačí vrátit přibližný medián, tedy prvek větší než např. 45 % jiných prvků a menší než 45 % jiných prvků.