Понижение оценки 𝛀(log n) для упорядоченного множества при работе с целыми числами (Филипп Грибов)

Семинар по алгоритмам и структурам данных ФКН «Понижение оценки 𝛀(log n) на время выполнения основных операций с упорядоченным множеством при работе с целыми числами» В модели сравнений давно показано, что существует оценка 𝛀(log n) на время выполнения основных операций с упорядоченным множеством (insert, delete, lower_bound). Однако при работе с целыми числами, кроме операций сравнения, доступны арифметические и битовые операции с целыми числами. В RAM-модели все эти операции выполняются за 𝓞(1), что позволяет при работе с целыми числами не ограничиваться сравнениями и снизить время выполнения основных операций с упорядоченным множеством. На семинаре мы рассмотрим результат двух статей Fredman и Willard. В начале мы разберемся со структурой данных Fusion Tree, которая позволяет получить оценку 𝓞(log n / log log n) на операцию lower_bound в упорядоченном массиве целых чисел. После этого мы разберем структуру данных Q-tree, которая позволяет при проведенном предподсчете за 𝓞(n) хранить любые упорядоченные множества целых чисел размера не более 𝓞(log n / 5) и делать основные операции с множеством (insert, delete, lower_bound) за асимптотику 𝓞(1). На основе этой структуры данных строится большинство алгоритмов для целых чисел, которые понижают известные нижние оценки в модели сравнения. Мы рассмотрим некоторые из этих алгоритмов, в частности объединив Q-tree и B-дерево, научимся строить упорядоченное множество целых чисел произвольного размера, в котором все основные операции будут выполняться за 𝓞(log n / log log n). Выступает Филипп Грибов, преподаватель ФКН ВШЭ. 23 апреля 2024 Семинар по алгоритмам и структурам данных ФКН: ФКН: ​​ Подписывайтесь на нас: 📍 📍 📍