|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Igor Grigoriev 2:5030/861.21 22 Dec 2001 03:03:05 To : Evgenij Masherov Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- _______________________________________________________________________________ Эх не знаю с чего и начать... :( 21 декабря 2001 года (а было тогда 09:38) Evgenij Masherov в своем письме к Igor Grigoriev писал: EM> Боюсь, что в общем случае круче O(N log N) сравнений не бывает. Это EM> фундаментальное ограничение, следующее из теории информации. Данный EM> алгоритм (разбиение на маленькие, сортируемые в памяти куски, и EM> слияние с O(N) сравнениями каждое, всего O(log N) слияний) как раз и ^^^^^^^^^^^^^^^^^^^^ Hе каждое, а все слияния дадут сложность O(N), так как Если поделить файл на b кусков, то придется делать N/b слияний со сложностью каждого O(b) => N/b*b=N. А логарифм - это сложность сортировки одного куска. ИМХО. Подсчет сложности алгоритма быстрой сортировки не берусь доказывать, так как забыл. EM> дает такой результат. Алгоритмы, в которых элементарный шаг не EM> сравнению, могут потребовать меньше шагов, но они требуют EM> дополнительной информации (скажем, 100 различных чисел в диапазоне EM> 1..256 могут быть отсортированы просто помещением их в EM> массив [1..256], предварительно заполненный нулями и затем переносом EM> их в массив из 100 элементов). Для таких может быть достигнута EM> теоретически минимальная сложность O(N) операций (не сравнений!) np: Тишину Igor --- GoldED+/W32 1.1.5-20010807 [Team Hackers] * Origin: Do not shoot the programmer... (2:5030/861.21) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/38973c23c297.html, оценка из 5, голосов 10
|