Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 16.08.2009, 20:16
Новичок

Отправить личное сообщение для motz-art Посмотреть профиль Найти все сообщения от motz-art
 
Регистрация: 16.08.2009
Сообщений: 6

Повторная сортировка (или сортировка после изменений)
Задача коротко.
Есть отсортированный массив. Некоторые его значения увеличились.
Вопрос: какой алгоритм даст лучшие результаты?

Детали(если важно)
  1. Сейчас массив содержит 50 тыс. элементов, в будущем дойдет до 1 млн.
  2. Содержит числа, с плавающей точкой в диапазоне от 0 до p1 (p1 - параметр и в данный момент равен 1)
  3. Причем количество разных значений относительно ограничего (сейчас около 1000).
  4. Измениться может до 90% элементов.
  5. Изменение=x*p2 где x-целое число от 1 до 10 и p2 - число с плавающей точкой, константа.
Если что упустил спрашивайте.
  #2  
Старый 16.08.2009, 23:12
гость

 
Сообщений: n/a

Используй сбалансированные двоичные деревья, тогда каждое изменение значений элементов займет O(log n) времени. Отсортированный массив в любой момент можно из дерева восстановить простым обходом. Если нужно обращаться к элементу по индексу (т.е. находить k-й наименьший элемент), то эту возможность также относительно легко можно реализована в любом дереве со сложность O(h), где h = высота дерева (O(log n) в случае сбалансированных)
  #3  
Старый 17.08.2009, 00:32
Новичок

Отправить личное сообщение для motz-art Посмотреть профиль Найти все сообщения от motz-art
 
Регистрация: 16.08.2009
Сообщений: 6

Огромное спасибо за ответ.
Прочитал про АВЛ деревья, очень интересная вещь. Исходя из того, что сложность изменения O(log n) а мне надо выполнить до 90% изменений, то общее время выполнения займет 0.9 n O(log n) или 90% времени повторной сортировки. А это не самая радосная перспектива. Если б была возможность значительно сократить количество изменений....

Кстати как ни странно повторная сортировка при проверке на практике сработала быстрее чем первая, когда массив был заполнен полностью случайными значениями.

Еще одна деталь
Из отсортированного массива меня интересуют только m елементов с наибольшим значением.
  #4  
Старый 17.08.2009, 00:49
гость

 
Сообщений: n/a

Сообщение от motz-art Посмотреть сообщение
Огромное спасибо за ответ.
Прочитал про АВЛ деревья, очень интересная вещь. Исходя из того, что сложность изменения O(log n) а мне надо выполнить до 90% изменений, то общее время выполнения займет 0.9 n O(log n) или 90% времени повторной сортировки.

А это не самая радосная перспектива. Если б была возможность значительно сократить количество изменений....
Меньше чем O(n log n) нельзя, это нижняя граница на время работы любого алгоритма сортировки (использующего только операции попарного сравнения элементов).
Если в массиве изменяется c*n элементов, для некоторой константы 0 < c <= 1 (у вас - c=0.9), то алгоритм, обрабатывающий все эти изменения быстрее чем за O(n log n), мог бы быть использован для создания алгоритма сортировки произвольного массива со сложностью лучше чем O(n log n), что невозможно.

Цитата:
Еще одна деталь
Из отсортированного массива меня интересуют только m елементов с наибольшим значением.
Храни в дереве только m наибольших элементов (т.е. при добавлении нового, m+1-го элемента, удаляй наименьший элемент из дерева), тогда будет сложность O(log m) на изменение, а общая сложность - O(n log m).

Вместо двоичных деревьев здесь также можно воспользоваться структурой данных двоичная куча (binary heap, используется в алгоритме сортировки heapsort) - она обеспечит ту же самую сложность O(n log m), но проще в написании, и раза в 2-3 быстрее.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сортировка стека гость Сортировка и поиск 4 25.09.2008 19:48
Сортировка массива Amir Математические алгоритмы (другое) 4 05.06.2008 15:59
Сортировка в файле... Прохожий Сортировка и поиск 3 26.05.2008 14:07
Сортировка ICEMAN Математические алгоритмы (другое) 3 06.12.2007 14:29
что за сортировка индексом? andrey Сортировка и поиск 2 25.10.2006 22:42