Dotaz: Knihovna pro rychlé nalezení mediánu v C

[Thunder.m]

Potřeboval bych co nejrychleji vypočítat medián 1D pole (floating point), zkoušel jsem funkce

qsort - velmi pomalá, cca 2 minuty navíc pro můj program

gsl_sort + gsl_stats_median_from_sorted_data - pomalá, cca 40 vteřin navíc

Existuje něco rychlejšího? Algoritmus quickselect mi vycházel ještě výrazně pomalejší.

Odpovědi

[fsgsfg]

Je to znamy algoritmus.. je napsany treba ve Wirth: Algorithms+data = programs nebo (myslim) v druhem dile the Art of... narocnost ma asi n log(n).

[Martin Tůma]

Složtost O(nlog(n)) má i seřazení pole (O(nlog(n))) a výběr prostředního prvku (O(1)). Složitost výpočtu medianu je ale pouze O(n), viz wikipedia.

[Thunder.m]

Ještě jsem zapomněl uvést že nynější náročnost není vysoká, vpodstatě výpočet průměru všech hodnot pole, ale rád bych použil medián, protože je přesnější.