OT: slozitost razeni primym zatridovanim

[Jirka Kosek]

Libor Chocholaty 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.

-----------------------------------------------------------------
  Jirka Kosek  	                     
  e-mail: jirka na kosek.cz
  http://www.kosek.cz