|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Andrew Simontsev 2:5005/115.41 21 Dec 2001 15:33:16 To : Igor Grigoriev Subject : Гоpодская олимпиада по инфоpматике --------------------------------------------------------------------------------
Thursday, December 20 2001 10:39, Igor Grigoriev wrote to Evgenij Masherov:
EM>> O(n) - вот и вся сложность...
EM>> Два отсортированных куска (для определенности - по возрастанию), берем
EM>> первые элементы, сравниваем, меньший пишем и продвигаемся по
EM>> соответствующему файлу, затем продолжаем сравнивать вновь прочитанные
EM>> (если в одном из файлов достигнут конец - переписываем остаток
EM>> другого). Кстати, алгоритму этому, кажется скоро будет 100 лет - он
EM>> был реализован в автоматическом подборщике перфокарт ИБМ в начале ХХ
EM>> века...
IG> Hо это портит логарифмическую сложность сортировки? Ведь O(n) - это не
IG> супер. Все равно что поиск проводить не дихитомией, а линейно. А по круче
IG> нет?
У сортировок сложность не log(n), а n*log(n)... Есть разница как бы ;)
Bye, Igor.
Sincerely yours, Andrew.
Играет cимФония Глюка на клавиатуре :-)
... I'm a VooDoo Chile!
--- Добрых дел мастер 3.0.1 лет ----------------------------------
* Origin: Меняю комнатную собачку на двухкомнатную. (2:5005/115.41)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/38793c23485d.html, оценка из 5, голосов 10
|