Ahojte. Mam taky mensi problem s dokazom dolneho odhadu zlozitosti triedenia. Rozumiem tomu viac menej celemu, len jedna vec mi furt nedochadza.

Nacrtnem tu danu problematiku:

Uvazujeme o triedeni ako o binarnom strome, v ktoreho listoch sa nachadzaju jednotlive operacie porovnani. Pre n prvkov bude mat dany strom aspon n! listov. Preto mozme pre strom vysky h uvazovat s maximalne 2^h listamy.

Kedze vieme toto pre jeho vysku bude platit: 2^h >= n!

2^h >= n! / log (uvazujeme s log pri zaklade 2)
h log 2 >= log n!
h >= log n!


Kedze n! rozpisane na jednotlive cinitele obsahuje n/2 cinitelov, ktory su vacsi rovno ako n/2, tak plati: n! >= (n/2)^(n/2)
k tomuto mam este otazku ako je to pri neparnom n ? zaokruhli sa nahor?

To mozme nasledne upravit na tvar:

n! >= (n/2)^(n/2) / log
log n! >= (1/2)*(log n - log 2)
log n! >= (1/2)*(log n - 1)


Vdaka tymto dvom faktom, tiez plati:

h >= log n! >= log n! >= (1/2)*(log n - 1)

a odtialto som nepochopil odkial sa vzalo to zvyraznene

pre vsetky n >= 4 : (1/2)(n*logn - 1) >= (1/4)*n*log n; a teda pre vsetky n >= 4 : h >= (1/4)*n*log n

no a toto je to hlavne, preco pisem. netusim aka uprava/uvaha viedla k tomuto zapisu a zaveru


Za pomoc vopred dakujem

Pripadne postrehy/korektury su vitane.