Approximate sorting

Молимо вас користите овај идентификатор за цитирање или овај линк до ове ставке: https://open.uns.ac.rs/handle/123456789/11952

Назив:	Approximate sorting
Аутори:	Giesen J. Schuberth E. Stojaković, Miloš
Датум издавања:	9-мар-2009
Часопис:	Fundamenta Informaticae
Сажетак:	We show that any comparison based, randomized algorithm to approximate any given ranking of n items within expected Spearman's footrule distance n^{2}/ν(n) needs at least n (min{log ν(n), log n} - 6) comparisons in the worst case. This bound is tight up to a constant factor since there exists a deterministic algorithm that shows that 6n log (n) comparisons are always sufficient.
URI:	https://open.uns.ac.rs/handle/123456789/11952
ISSN:	01692968
DOI:	10.3233/FI-2009-0005
Налази се у колекцијама:	PMF Publikacije/Publications