Персистентная очередь

Спасибо. Если не секрет, какой алгоритм вы проходили, с кучей стеков?

Интересно. Но что-то я не могу прикинуть в уме асимптотику — у нас получается же O(n) амортизированное?

Если вы про теоретическое описание, то нет, никакой амортизационный анализ не применяется, каждый запрос выполняется строго за O(1), об этом даже где-то по тексту написано. Если же вы про мою реализацию, то да, там в силу использования вектора для хранения очередей, каждый push или pop выполняется за амортизированное O(1). Естественно, можно обойтись и без него, например, используя односвязный список и выдавая указатель на его элемент вместо числового id, я использовал вектор для упрощения и соответствия интерфейсу теоретического описания.

И какой порядок константы перед этим самым n?

В каких единицах надо это оценить?

Начиная с какого порядка размера очереди она начнёт выигрывать по производительности у O(n*log(n)), которая явно проще в реализации?

Что вы имеете в виду под простой реализацией за O(n log n): реализацию с помощью персистентного дерева поиска по неявному ключу? По-хорошему, надо просто написать и сравнить. Но осмелюсь предположить, что на данных, при которых эти реализации будут быстрее наивной за n², мой алгоритм всегда будет выигрывать. Почему я так считаю? Потому что при добавлении или удалении вершины из персистентного дерева (операции push и pop, соотвественно), мы вынуждены будем создать копию каждой вершины на пути до корня. А на таких данных, длина этого пути будет не меньше 10 (она порядка log n). Впрочем, это лишь гипотеза. К слову, я не считаю её явно проще в реализации, она скорее проще в понимании, потому что от неперсистентного варианта почти не отличается, объем же кода будет примерно одним и тем же.