Предположим, что в нашем распоряжении есть алгоритм, который за линейное время находит медиану массива. Алгоритм не изменяет массив и выдает индекс ячейки исходного массива, в которой стоит медиана. Покажите, как использовать этот алгоритм, чтобы за линейное же время найти любую заданную порядковую статистику массива.

задан 29 Ноя '15 2:11

изменен 29 Ноя '15 2:11

Что понимается под заданной порядковой статистикой?

(29 Ноя '15 3:42) falcao
10|600 символов нужно символов осталось
4

Ищем медиану и создаем новый массив, ставим ее посередине. Слева от нее поставим все элементы, которые меньше медианы, справа - те, которые больше. Всего мы выполнили $%Cn$% действий (C-какая-то константа). Теперь если запрошенная порядковая статистика $%k<\frac{n}{2}$%, делаем тоже самое с левой частью массива. Если больше, то с правой, пересчитав $%k=k-\frac{n}{2}$%. Если $%k=\frac{n}{2}$%, то найденная медиана и есть запрошенная порядковая статистика. Каждый раз мы ищем статистику в массива, который в два раза меньше предыдущего. Итого $%C(n+\frac{n}{2}+\frac{n}{4}+\cdots)< C2n$% действий, 2 - константа, которую можно убрать в $%C$% $%\Rightarrow $% асимптотика $%O(n)$%. Нужно только обратить внимание на случай, когда $%n$% - четное, но это детали реализации.

ссылка

отвечен 29 Ноя '15 5:14

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×296
×286
×210
×103
×83

задан
29 Ноя '15 2:11

показан
1598 раз

обновлен
29 Ноя '15 5:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru