OT: slozitost razeni primym zatridovanim

[Petr Kolar]

Jirka Kosek <jirka na kosek.cz> wrote:
> > kolega ma problem, potrebuje vedet, jakou slozitost ma razeni
> > zatridovanim, muzete mu nekdo pomoci?
> > Vime, ze je to lepsi nez bubble-sort (n^2) a horsi nez quick-sort
> > (n*log(n))...
> 
> Ze to je lepsi nez bubble-sort bych si nebyl uplne jisty. Pokud maji
> razene hodnoty rovnomerne rozdeleni, je casova slozitost n^2, kdyby se
> to vyjadrilo presneji tak to vyjde odhadem okolo 0.25*n^2, ale porad je
> to kvadraticka slozitost. Konstanta, kterou se slozitost nasobi, se ve
> vetsine pripadu neuvazuje.

Ale zrovna pri porovnavani algoritmu, ktere maji tu mocninu stejnou, je ta
konstanta docela zajimava.

Kdyz se mluvi o slozitosti tak by se melo rict, jaka slozitost se mysli,
jestli v nejhorsim, strednim nebo nejlepsim pripade. Dobre napsany 
bubblesort pusteny na setridenou posloupnost je lepsi nebo stejne dobry
nez jine algoritmy (lepsi nez quicksort a heapsort), quicksort ma spatny
nejhorsi pripad, ale mimoradne dobry stredni pripad (i co se tyce te
nasobici konstanty). U quicksortu navic zalezi na zpusobu vyberu pivota.

Kdyz necham tech reci okolo, tak podle tech informaci v otazce (bubblesort
n^2, quicksort n.log(n)) se ptate na stredni slozitost, kterou ma prime
zatridovani k.n^2 jako bubblesort, ale jak vypada ta konstanta (pokud to
vubec je konstanta - ta konstanta v v podstate jenom horni odhad nejake
funkce n) v porovnani s bubblesortem nevim. :- (

                                                  S pozdravem
--
                          ***  Petr Kolar  ***
 Department of Information Technologies, Technical University of Liberec
             Voronezska 1329, 461 17 Liberec, Czech Republic
             Phone: +420-48-535-2371   Fax: +420-48-535-2229
      E-mail: Petr.Kolar na vslib.cz  http://www.kit.vslib.cz/~kolar/