Вопрос (возможно, боян и не в тот раздел)
пузырек с двух сторон? 
quick sort
если ниче не путаю - самые продвинутые сортировки - сортировки сетями компараторов.
дают сложность O( (ln n)^2 ).
дают сложность O( (ln n)^2 ).
Спасибо, с бинарными вставками уже разобрался 
!
!quick sortА ссылки или алгоритм можно?
если ниче не путаю - самые продвинутые сортировки - сортировки сетями компараторов.Ничего себе! Можешь ссылку дать? (А то гугль сразу ерунду какую-то дает)
дают сложность O( (ln n)^2 ).
Не слушай его, он написал поебень.
может быть что-то путаю... не спорю. но вроде читал что-то подобное...
дома книга есть по алгоритмам - посмотрю подробнее.
дома книга есть по алгоритмам - посмотрю подробнее.
попутал.
O(n*log(n
доказательство нетрудное
O(n*log(n
доказательство нетрудное
Не слушай его, он написал поебень.А я уже было обрадовался.
нет, вроде не попутал.
O(n*log(n - а такую сложность вроде обычный квиксорт дает...
O(n*log(n - а такую сложность вроде обычный квиксорт дает...
да действительно.
трэд жесть. десант из ФДСа?
для квиксорта O(n*logn) - сложность в среднем, O(n*n) - в худшем случае
для сортировки слиянием O(n*logn) - сложность в худшем случае (насколько помню это дело)
повторяю: несложно доказать, что быстрее O(n*logn) нет сортировки. Кнут тебе поможет
для сортировки слиянием O(n*logn) - сложность в худшем случае (насколько помню это дело)
повторяю: несложно доказать, что быстрее O(n*logn) нет сортировки. Кнут тебе поможет
сортировки сетями компараторов
Видимо, это не сортировка на привычном языке программирования. Поэтому и сложность может быть запросто меньше NlogN
Но, насколько я понимаю, это из серии чего-то реального (вычислительных схем каких-то а не квантовых компьютеров и т.п.
И вообще NlogN - это общий алгоритм сортировки. Маленькие числа можно сортировать подсчетом, большие - побайтно (проверено, что работает в разы быстере quick sort'а вещественные - вычерпыванием. Вообще таких алгоритмов существенно больше, чем я назвал
для квиксорта O(n*logn) - сложность в среднем, O(n*n) - в худшем случае
Для самого простого Qsort'а - да. Но смотря как писать. Например, в некоторых верисиях Sort STL ограничивается глубина рекурии (в зависимости от размера данных и если она превышена (подставный тест сломал рэндом запускается другой алгоритм (MergeSort, насколько я помню).
FlashSort O(n)
http://www.neubert.net/FSOIntro.html
http://www.neubert.net/FSOIntro.html
если ниче не путаю - самые продвинутые сортировки - сортировки сетями компараторов.кстати на каком то из спец семов на мм както чувак покаывал сортировку O( (ln n)^1.86 ).
дают сложность O( (ln n)^2 ).
только она вероятностная была.
кстати на каком то из спец семов на мм както чувак покаывал сортировку O( (ln n)^1.86 ).только она вероятностная была.На чем он так сортировал? И что сортировал?
Явно ж не на С++
Я тоже могу постоить модель с сортировкой О(1):
Есть N! гениев и телепатов. Они распределяют между собой все перестановки (вообще до своего рождения еще потом каждый по телепатической связи берет свою (за О(1 они же гении и тот, кто понял, что его отсортирована (тож за О(1 громко кричит "Свинья"!
не ну вероятность правильности тоже показывали. кстати чувак кандидатскую по этой теме защитил.
Оставить комментарий
Fofa
Какой есть оптимальный алгоритм упорядочивания элементов массива по возрастанию?(Пузырек уж очень долгий)