|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Evgenij Masherov 2:5020/175.2 21 Dec 2001 10:38:32 To : Igor Grigoriev Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- Thu Dec 20 2001 10:39, Igor Grigoriev wrote to Evgenij Masherov: YK>>>> Стандартными методами _внешней_ сортировки. YK>>>> Самое простое - разбиваем файл на куски, которые влезают в YK>>>> память, сортируем каждый кусок qsort, потом сливаем YK>>>> отсортированные куски. Примерно так, AFAIK, работает sort из gnu YK>>>> textutils на *больших* файлах. IG>>> Как сливаем, по подробнее? Если один в конец другого - то не IG>>> верно, если нет, то алгоритм с подсчетом сложности в студию. EM>> O(n) - вот и вся сложность... EM>> Два отсортированных куска (для определенности - по возрастанию), берем EM>> первые элементы, сравниваем, меньший пишем и продвигаемся по EM>> соответствующему файлу, затем продолжаем сравнивать вновь прочитанные EM>> (если в одном из файлов достигнут конец - переписываем остаток EM>> другого). Кстати, алгоритму этому, кажется скоро будет 100 лет - он EM>> был реализован в автоматическом подборщике перфокарт ИБМ в начале ХХ EM>> века... IG> Hо это портит логарифмическую сложность сортировки? Ведь O(n) - это не IG> супер. Все равно что поиск проводить не дихитомией, а линейно. IG> А по круче нет? Боюсь, что в общем случае круче O(N log N) сравнений не бывает. Это фундаментальное ограничение, следующее из теории информации. Данный алгоритм (разбиение на маленькие, сортируемые в памяти куски, и слияние с O(N) сравнениями каждое, всего O(log N) слияний) как раз и дает такой результат. Алгоритмы, в которых элементарный шаг не сравнению, могут потребовать меньше шагов, но они требуют дополнительной информации (скажем, 100 различных чисел в диапазоне 1..256 могут быть отсортированы просто помещением их в массив [1..256], предварительно заполненный нулями и затем переносом их в массив из 100 элементов). Для таких может быть достигнута теоретически минимальная сложность O(N) операций (не сравнений!) Евгений Машеров АКА СанитарЖеня --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/330008b63a32.html, оценка из 5, голосов 10
|