mq
типа пишешь и оно магическим образом может работать гораздо быстрее
Size: a a a
2020 May 22
MB
насколько я понимаю можно легко писать сплеи вместо декартачей и вообще просто вместо стандартного сета
Ну, мне не кажется что сплей проще декартача.
mq
ну он не проще, но я просто столько хороших вещей про него услышал что странно что никто не написал пбдс-стайл библиотеку для спортпроги
mq
которую копипастишь и оно хорошо работает
MB
То, что сплей может работать за O(N) - ну это должно отсекаться хорошими тестами.
mq
так он не может работать за О(н)
mq
там амортайзд лог
mq
типа у тебя асимптотика будет всегда гарантированно эм лог н
mq
типа против него контртестов не придумать, как против декартача
MB
так он не может работать за О(н)
Насколько я помню, если все запросы будут попадать в вершины, близкие к корню (на глубине O(1)), то сплей просто вынужден работаь за O(N)
mq
потому что ребята слетор и тарьян доказали что ворст-кейс амортайзд лог
mq
Насколько я помню, если все запросы будут попадать в вершины, близкие к корню (на глубине O(1)), то сплей просто вынужден работаь за O(N)
не, ты не прав
mq
потому что ребята слетор и тарьян доказали что ворст-кейс амортайзд лог
а рядом еще куча результатов о том как классно он работает если тебе повезло с запросами
e
Какой лучше алгоритм использовать для нахождения площади пересечения прямоугольника и многоугольника?
mq
не, ты не прав
всегда после m запросов к n ключам верхняя граница суммарных операций O(m log n)
MB
не, ты не прав
Так, рассмотрим сплей, в котором N раз поискали значение, лежащее в корне.
Каждый раз мы будем запускать спуск по дереву, который за 1=O(1) итераций отыщет вершину - корень.
Далее мы запускаем от корня expose, который работает за размер пути от вершины до корня, то есть за O(1).
Итого O(1) на запрос.
Где я не прав?
Каждый раз мы будем запускать спуск по дереву, который за 1=O(1) итераций отыщет вершину - корень.
Далее мы запускаем от корня expose, который работает за размер пути от вершины до корня, то есть за O(1).
Итого O(1) на запрос.
Где я не прав?
mq
то что на некоторых может быть n или 100n или что угодно вообще поебать
mq
Так, рассмотрим сплей, в котором N раз поискали значение, лежащее в корне.
Каждый раз мы будем запускать спуск по дереву, который за 1=O(1) итераций отыщет вершину - корень.
Далее мы запускаем от корня expose, который работает за размер пути от вершины до корня, то есть за O(1).
Итого O(1) на запрос.
Где я не прав?
Каждый раз мы будем запускать спуск по дереву, который за 1=O(1) итераций отыщет вершину - корень.
Далее мы запускаем от корня expose, который работает за размер пути от вершины до корня, то есть за O(1).
Итого O(1) на запрос.
Где я не прав?
в том что есть статья слетора и тарьяна, где они доказали что оно работает как надо
mq
Так, рассмотрим сплей, в котором N раз поискали значение, лежащее в корне.
Каждый раз мы будем запускать спуск по дереву, который за 1=O(1) итераций отыщет вершину - корень.
Далее мы запускаем от корня expose, который работает за размер пути от вершины до корня, то есть за O(1).
Итого O(1) на запрос.
Где я не прав?
Каждый раз мы будем запускать спуск по дереву, который за 1=O(1) итераций отыщет вершину - корень.
Далее мы запускаем от корня expose, который работает за размер пути от вершины до корня, то есть за O(1).
Итого O(1) на запрос.
Где я не прав?
поботай амортизацию)0))))))))))))))
MB
всегда после m запросов к n ключам верхняя граница суммарных операций O(m log n)
Я не спорю с тем, что у сплея хорошая верхняя граница. Но она не лучше времени работы асимптотики декартача.