funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
komentáře článku 

Mergeselect



Text komentáře


v6ak (2016-08-23 09:39)
"Chci najít m-tý nejmenší element, jinými slovy potřebuji najít prvek, kterému předchází m menších bratří."

Není to spíše prvek, kterému předchází m-1 menších bratří?

Nemám teď úplně pocit, že jsem to pochopil, ale:
• Co když k=1? Bude i zde platit tato slozitost?
• Pokud je asymptotická slozitost založená na pravděpodobnosti, nedostaneš worst-case, ale spíše průměr. V tomto směru na tom ale je stejně jako QuickSelect, ne?


k47 (2016-08-23 13:37)
m nebo m-1, záleží jestli indexy začínají od 0 nebo 1. Ale máš pravdu, m-1 dává smysl.

k=1 je stejně patologický případ jako k=n a pro ně to fungovat nebude.

Přesně tak, nejde o nejhorší případ, ale o ten očekávaný, stejně jako quickselect. Doplnil jsem to do textu.


v6ak (2016-08-23 15:21)
Pokud je řeč o počtu prvků, pak je jedno, jestli začínají od nuly, nebo od jednicky.

No, k ani nemůže být zvoleno tak, aby se obecně rovnalo n, pokud není počet prvků předem znám. A pokud je, pak vše děláme v O(1), až na výjimky, kde máme O(∞). Pak ale asymptotická složitost vlastně říká jen to, zda je garantováno nebo časově omezeno dokončení algoritmu. Pokud bychom k vybrali az podle délky vstupu, uz by to nebyla konstanta, takže by slo o jiný algoritmus.

Varianta k=1 by ale nemusela být patologická, pokud sekvence nebude začínat největším prvkem. (Podobný problém může nastat i u většího k, jen s nižší pravděpodobností.)


k47 (2016-08-27 19:32)
Když *k = n*, pak to běží v čase *n log(n)*, protože udělám jeden průchod mergesortu, seřadím vstupní kolekci a hotovo vyberu *m*-tý prvek.

Když *k = 1*, stane se z toho svým způsobem quickselect. První blok velikosti 1 je pivot, použitý pro filtrování ostatních singulárních bloků.


v6ak (2016-08-28 06:19)
k = n (nebo obecneji k≥n): Jak se to vezme. Pokud se pred spustenim podivam na delku kolekce, a takto zvolim k, pak ano, ale je to uz jiny algoritmus. Pokud jde o to, ze pro nekdere male vstupy to takto vyjde, tak to nema na asymptotickou analyzu zadny vliv :)

k=1: Asi ano, ale z hlediska asymptoticke slozitosti to patologicke neni, ne? Prumer bude porad O(n) a worst-case je IMHO dosazitelny i u vetsich k, pokud se ty nejvetsi prvku dostanou do prvniho bloku.


@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články