"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?
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í.)
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.
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?
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.