PostgreSQL

[Pavel Kankovsky]

On Fri, 1 Oct 1999, Oto tapik Buchta wrote:

> No mne by hlavne zajimalo, jestli ten dotycny vi, jak dlouho mu bude
> trvat sort na 10^10 zaznamech. I pri slozitosti n.log(n) (zatim imho
> nejlepsi, ceho se da dosahnout) je to neco kolem 10^11 kroku.

Da se dokazat, ze O(n log n) je asymptoticky nejlepsi mozna slozitost,
pokud se vyuziva pouze porovnavani prvku (to je btw dulezity
predpoklad...ve specialnich situacich lze tridit i s linearni slozitosti).

Dukaz je celkem jednoduchy: mame-li seznam n prvku, pak muze prijit v n!
ruznych setridenich. Tj. algoritmus musi byt schopen provest n! ruznych
permutaci, tj. musi provest alespon O(log n!) rozhodnuti, jak dal (na
zaklade porovnani prvku), coz se za pouziti Stirlingova vzorce da
prepocitat na O(n log n).

Snad tato mala comp-sci odbocka nikomu nebude vadit.

--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."