|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Igor Grigoriev 2:5030/861.21 20 Dec 2001 11:39:42 To : Evgenij Masherov Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- _______________________________________________________________________________ Сегодняшний день прошел безразвратно. 18 декабря 2001 года (а было тогда 09:33) Evgenij Masherov в своем письме к Igor Grigoriev писал: YK>>> Стандартными методами _внешней_ сортировки. YK>>> Самое простое - разбиваем файл на куски, которые влезают в YK>>> память, сортируем каждый кусок qsort, потом сливаем YK>>> отсортированные куски. Примерно так, AFAIK, работает sort из gnu YK>>> textutils на *больших* файлах. IG>> Как сливаем, по подробнее? Если один в конец другого - то не IG>> верно, если нет, то алгоритм с подсчетом сложности в студию. EM> O(n) - вот и вся сложность... EM> Два отсортированных куска (для определенности - по возрастанию), берем EM> первые элементы, сравниваем, меньший пишем и продвигаемся по EM> соответствующему файлу, затем продолжаем сравнивать вновь прочитанные EM> (если в одном из файлов достигнут конец - переписываем остаток EM> другого). Кстати, алгоритму этому, кажется скоро будет 100 лет - он EM> был реализован в автоматическом подборщике перфокарт ИБМ в начале ХХ EM> века... Hо это портит логарифмическую сложность сортировки? Ведь O(n) - это не супер. Все равно что поиск проводить не дихитомией, а линейно. А по круче нет? np: Тишину С наилучшими пожеланиями, Igor --- GoldED+/W32 1.1.5-20010807 [Team Hackers] * Origin: Если у Вас нет проблем - значит, Вы уже умерли. (2:5030/861.21) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/38973c21965c.html, оценка из 5, голосов 10
|