Страница 1 из 1

Вопрос для разминки кодерам

СообщениеДобавлено: Ср сен 03, 2014 1:28 pm
apprentice
Есть массив чисел типа float длиной n, где n нечетное. Диапазон значений чисел заранее неизвестен, закон распределения тоже неизвестен.
Нужно найти медиану , значение следующее за медианой, и т.д. до значения стоящего на месте n/2+lg(n), результат должен быть отсортирован по возрастанию.

Требуемая сложность по времени исполнения - O(n), доп. память не более О(n).

Уточню -- если отсортировать весь массив, то надо вернуть его часть которая начинается по указателю int(n/2)+1 и заканчивается по указателю int(n/2)+int(lg(n))+1.

Re: Вопрос для разминки кодерам

СообщениеДобавлено: Чт сен 04, 2014 6:34 am
zxweed
http://www.stat.cmu.edu/~ryantibs/papers/median.pdf

In many important problems, one uses the median instead of the mean to estimate a population’s center, since the former is more robust. But in general, computing the median is considerably slower than the standard mean calculation, and a fast median algorithm is of interest. The fastest existing algorithm is quickselect.

We investigate a novel algorithm binmedian, which has O(n) average complexity. The algorithm uses a recursive binning scheme and relies on the fact that the median and mean are always at most one standard deviation apart. We also propose a related median approximation algorithm binapprox, which has O(n) worst-case complexity. These algorithms are highly competitive with quickselect when computing the median of a single data set, but are significantly faster in updating the median when more data is added.

Re: Вопрос для разминки кодерам

СообщениеДобавлено: Чт сен 04, 2014 6:48 am
apprentice
zxweed, это еще не решение задачи, т.к. надо найти сразу несколько порядковых величин, от int(n/2)+1 до int(n/2)+int(lg(n))+1

Re: Вопрос для разминки кодерам

СообщениеДобавлено: Чт сен 04, 2014 6:50 am
apprentice
см. книгу в аттаче.

решение

СообщениеДобавлено: Вт сен 09, 2014 7:27 am
apprentice
решение:
1. запускаем quickselect с параметром - медиана, в результате получаем частично упорядоченный массив, так что правая часть его будет больше медианы, время O(n).
2. снова запускаем quickselect на правой половине массива с параметром int(n/2)+int(lg(n))+1, в результате участок между медианой и int(n/2)+int(lg(n))+1 будет содержать требуемые для нас значения., время O(n).
3. сортируем участок между медианой и int(n/2)+int(lg(n))+1 быстрым алгоритмом со сравнениями - quicksort, mergesort, heapsort, сложность O(m lg m) где m=lg n, следовательно время O(n).