|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Evgenij Masherov 2:5020/175.2 24 Dec 2001 12:00:11 To : Igor Grigoriev Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- Sat Dec 22 2001 02:03, Igor Grigoriev wrote to Evgenij Masherov: EM>> Боюсь, что в общем случае круче O(N log N) сравнений не бывает. Это EM>> фундаментальное ограничение, следующее из теории информации. Данный EM>> алгоритм (разбиение на маленькие, сортируемые в памяти куски, и EM>> слияние с O(N) сравнениями каждое, всего O(log N) слияний) как раз и IG> ^^^^^^^^^^^^^^^^^^^^ IG> Hе каждое, а все слияния дадут сложность O(N), так как Если поделить файл IG> на b кусков, то придется делать N/b слияний со сложностью каждого O(b) => IG> N/b*b=N. А логарифм - это сложность сортировки одного куска. ИМХО. IG> Подсчет сложности алгоритма быстрой сортировки не берусь доказывать, так IG> как забыл. Да, но на каждом шаге сливаются b кусков по N/b длиной, так что O(N). А сортировка требует не менее O(log N) проходов. Евгений Машеров АКА СанитарЖеня --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/330009b822da.html, оценка из 5, голосов 10
|