2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Структура для удаления половины наибольших элементов
Сообщение19.07.2011, 00:26 
Здравствуйте.

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


Понятно, что если 2-ую операцию реализовать за время $O(n)$, то условие будет выполнено.
Даже ясна одна из реализаций: нужно удалить - считаешь медиану (такой элемент, что в упорядоченном множестве находился бы посередине(или один из элементов, если их несколько) множества и разбиваешь на 2 половинки: больше её и меньше, большую удаляешь. Для нахождения медианы есть детерминированный алгоритм, работающий за $O(n)$, а для второго достачно и вовсе одного пробега по массиву. Т.е. условие выполнено.
Но проблема в том, что для нахождения медианы хоть и требуется линейное время, но коэффицент очень велик, поэтому поступать так не очень хорошо, и, скорее всего, есть другое решение. Подскажите, пожалуйста.

Спасибо.

p.s. задача из книги Кормен "Алгоритмы, построение и анализ".

 
 
 
 Re: Структура для удаления половины наибольших элементов
Сообщение19.07.2011, 02:58 
список?

 
 
 
 Re: Структура для удаления половины наибольших элементов
Сообщение19.07.2011, 09:54 
Как вы там удалите $\frac{n}{2}$ наибольших элементов за $O(n)$?
Удалите-то точно за $O(n)$, но наибольших ли.

Может я чего-то не понял. Поясните поподробней, пожалуйста.

 
 
 
 Re: Структура для удаления половины наибольших элементов
Сообщение19.07.2011, 17:26 
Возьму двусвязный список. Буду поддерживать инвариант, что список упорядоченный. Вставка в список $O(n)$, максимальный элемент всегда в конце, поэтому удаление происходит за $O(1)$.

 
 
 
 Re: Структура для удаления половины наибольших элементов
Сообщение19.07.2011, 19:40 
BanmaN в сообщении #469465 писал(а):
Здравствуйте.

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


Понятно, что если 2-ую операцию реализовать за время $O(n)$, то условие будет выполнено.
Даже ясна одна из реализаций: нужно удалить - считаешь медиану (такой элемент, что в упорядоченном множестве находился бы посередине(или один из элементов, если их несколько) множества и разбиваешь на 2 половинки: больше её и меньше, большую удаляешь. Для нахождения медианы есть детерминированный алгоритм, работающий за $O(n)$, а для второго достачно и вовсе одного пробега по массиву. Т.е. условие выполнено.
Но проблема в том, что для нахождения медианы хоть и требуется линейное время, но коэффицент очень велик, поэтому поступать так не очень хорошо, и, скорее всего, есть другое решение. Подскажите, пожалуйста.

Спасибо.

p.s. задача из книги Кормен "Алгоритмы, построение и анализ".
Собственно, вы уже решили задачу. $O(n)$ есть $O(n)$ независимо от коэффициента. Осталось выбрать структуру, которая позволит найти медиану с требуемой сложностью (список не подходит).

 
 
 
 Re: Структура для удаления половины наибольших элементов
Сообщение19.07.2011, 20:32 
Так да, только медиану я даже не представляю как поддерживать. Единственная идея - использовать две очереди с приоритетами (одну-возрастающую, другую - убывающую) и отдельно один элемент(медиану), но тогда вставка займёт $O(lg n)$.

Про коэффициент я к тому что такая реализация не пойдёт=).

Dmitriy_M, читайте внимательно главный пост. Там всё написано. Верхняя граница для вставки - $O(1)$.

 
 
 
 Re: Структура для удаления половины наибольших элементов
Сообщение20.07.2011, 00:08 
[quote="BanmaN в [url=http://dxdy.ru/post469676.html#p469676] Верхняя граница для вставки - $O(1)$.[/quote]
Вряд ли такая структура данных существует.

 
 
 
 Re: Структура для удаления половины наибольших элементов
Сообщение29.07.2011, 16:29 
Я нашёл сайт с решением и там написано то же самое, что и я сказал=)
Видимо, лучшего решения, значит, не найти...

Пруфлинк: http://courses.csail.mit.edu/6.046/fall01/handouts/ps7sol.pdf.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group