Самые красивые библиотеки мира 
Забавное 
Городские сюжеты 
18 апреля 2024 года состоялась церемония посвящения M10 Booker 
КУРИЦА С КАРТОШКОЙ 
Первоцветы у меня во дворе 
"Средневековые видения от VI по XII век" (Новое литературное обозрение, 2024) 
Неюбилейный Ефим Копелян
05.02.2010 —
О кнопке “закрыть окно” и немного о ОС вообще.
о сортировках
wizzard0 — 18.06.2010
уважаемые товарищи!
а почему все считают, что сортировка произвольных данных inplace
может выполняться за N log(N), если с
1985 1978
года у нас есть модификация бинарного поиска, работающая
за log(log(N))?
ведь тогда, даже если взять банальную сортировку
вставкой, асимптотика должна быть N*log(log(N)), или я чего-то
недопонимаю?
UPD: блин, сортировка вставкой ведь еще двигать элементы должна, а в связном списке interpolation search невозможен.. надо сделать вариант Library sort и померять.
UPD2: а вот и N log log N сортировка от Yijie Han – yijie.han-loglogn-sort.pdf, спасибо
![о сортировках [info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
184467440737095
за наводку. Надо бы реализовать и потестить))
Сохранено
|
|
</> |
Оставить комментарий
Популярные посты:
Предыдущие записи блогера :
31.01.2010 —
Провокационно о Linux
Архив записей в блогах:
Итак, президентом Дональдом Трампом подписан ежегодный акт консолидированных ассигнований Палаты представителей США на 2017 год. Длиннейший документ, где, в частности, прописан запрет оказывать финансовую помощь государствам, которые признали независимость " Южной Осетии ...
Израиль отзывает посла из Польши Израиль отзывает главу посольства в Варшаве из-за закона о реституции имущества пострадавших в годы Холокоста говорится в заявлении главы МИД еврейского государства Яира Лапида, распространенном его пресс-службой. Ранее президент Польши Анджей Дуда ...
"- Михаил, я хочу вас видеть в вашей квартире" , вообще, когда я слышу что-то подобное, то уже примерно понимаю, о чём собственно пойдет разговор. Однако в этот раз я ошибался, Алексей пригласил меня к себе совершенно с иной целью. Отложив все дела я примчал в Коммунарку, а там меня уже ...
Когда еще подъезжал к своему отелю в Турции, сразу обратил внимание - что это за полуразрушенный забор с "позолоченным" рисунком? Что то это мне напоминает. Где то слышал про это. Ну, а потом лежа в шезлонге у бассейна посмотрел в даль и ... ба, да это же знаменитый "Мардан Палас"! ...
Дмитрий Быков vs. Никита Михалков в программе Владимира Соловьёва ПОЕДИНОК одним куском скачать программу можно отсюда: http://narod.ru/disk/ 26698873000/Poedinok%2028.10. 10.avi.html ...
