We show that any comparison based, randomized algorithm to approximate any given ranking of n items within expected Spearman’s footrule distance n2/ν(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. Keywords: algorithms, sorting, ranking, Spearman's footrule metric, Kendall's tau metri
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.