Трейдерский Клуб

Общение о рынках, рисках и жизни. Без пиара и без рекламы. Здесь рады только своим.

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

Свободное общение. Предложения по работе форума.

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

Сообщение apprentice » Ср сен 03, 2014 1:28 pm

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

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

Уточню -- если отсортировать весь массив, то надо вернуть его часть которая начинается по указателю int(n/2)+1 и заканчивается по указателю int(n/2)+int(lg(n))+1.
apprentice
Зубр
 
Сообщения: 125
Зарегистрирован: Пт янв 28, 2011 5:28 pm

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

Сообщение zxweed » Чт сен 04, 2014 6:34 am

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.
zxweed
 
Сообщения: 74
Зарегистрирован: Сб авг 24, 2013 5:25 pm

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

Сообщение apprentice » Чт сен 04, 2014 6:48 am

zxweed, это еще не решение задачи, т.к. надо найти сразу несколько порядковых величин, от int(n/2)+1 до int(n/2)+int(lg(n))+1
apprentice
Зубр
 
Сообщения: 125
Зарегистрирован: Пт янв 28, 2011 5:28 pm

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

Сообщение apprentice » Чт сен 04, 2014 6:50 am

см. книгу в аттаче.
У вас нет необходимых прав для просмотра вложений в этом сообщении.
apprentice
Зубр
 
Сообщения: 125
Зарегистрирован: Пт янв 28, 2011 5:28 pm

решение

Сообщение apprentice » Вт сен 09, 2014 7:27 am

решение:
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).
apprentice
Зубр
 
Сообщения: 125
Зарегистрирован: Пт янв 28, 2011 5:28 pm


Вернуться в PUB: Курилка

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1