A
ну это не крутой приём)
Size: a a a
2020 August 23
A
кажется, что полная сортировка, в теории, не нужна
MB
Можно решить задачу two closest points на линии за O(n)? каким-нибудь хитрым рандомизированным алгоритмом, к примеру?
Т.е. просто даны n чисел и нужно найти два ближайших по модулю
Т.е. просто даны n чисел и нужно найти два ближайших по модулю
n раз выбираем случайную пару чисел. Получили n расстояний, из них выбираем наименьшее, обозначим за B.
Далее делим числа на блоки. В один блок дают числа, дающие одинаковое частное от деления на B (ну то есть мы сделали сеточку с шагом B и пронумеровали ячейки).
Дальше каждый блок сортируем, ну и теперь понятно как считать ответ.
У этого алгоритма линейное матожидание вроде
Далее делим числа на блоки. В один блок дают числа, дающие одинаковое частное от деления на B (ну то есть мы сделали сеточку с шагом B и пронумеровали ячейки).
Дальше каждый блок сортируем, ну и теперь понятно как считать ответ.
У этого алгоритма линейное матожидание вроде
MB
О, это же еще и сортировка за линию получилась, прикольно :)
DK
Это же вроде карманная сортировка?
CD
n раз выбираем случайную пару чисел. Получили n расстояний, из них выбираем наименьшее, обозначим за B.
Далее делим числа на блоки. В один блок дают числа, дающие одинаковое частное от деления на B (ну то есть мы сделали сеточку с шагом B и пронумеровали ячейки).
Дальше каждый блок сортируем, ну и теперь понятно как считать ответ.
У этого алгоритма линейное матожидание вроде
Далее делим числа на блоки. В один блок дают числа, дающие одинаковое частное от деления на B (ну то есть мы сделали сеточку с шагом B и пронумеровали ячейки).
Дальше каждый блок сортируем, ну и теперь понятно как считать ответ.
У этого алгоритма линейное матожидание вроде
почему B полином от 1/n?
V🇺
почему B полином от 1/n?
а зачем ему?
V🇺
О, это же еще и сортировка за линию получилась, прикольно :)
а корзины как упорядочить?
CD
а зачем ему?
Нехорошо делить на 2^n групп
V🇺
Нехорошо делить на 2^n групп
так тебе только непустые интересны
CD
так тебе только непустые интересны
А, ты имеешь в виду что мы нахешмапим?
V🇺
V🇺
и понятно почему это не сортировка
CD
и понятно почему это не сортировка
хм, а если я возьму log групп достаточно ровно и забинпоискирую принадлежность, я же получу сортировку n * log log n no matter what?
CD
а дальше возьму log log групп достаточно ровно, забинпоискирую принадлежность и получу n * log log log n no matter what?
CD
хм... я опять изобрел ван Эмде Боаса? :)
V🇺
хм... я опять изобрел ван Эмде Боаса? :)
похоже)
CD
надо уже счётчик числа изобретений
V🇺
А вот еще задачка: известно что произведение prod((x^2+ai*x+bi)/(x^2+ci*x+di)) в общем случае можно расписать как сумму членов того же вида. Вопрос, можно ли сделать это быстрее чем за квадрат?
CD
похоже)
а есть пруфы неулучшаемости собственно вана?