Динамизация
В информатике . динамизация это процесс преобразования статической структуры данных в динамическую — Хотя статические структуры данных могут обеспечивать очень хорошую функциональность и быстрые запросы, их полезность ограничена из-за их неспособности быстро увеличиваться/сжиматься, что делает их неприменимыми для решения динамических задач , когда входные данные изменяются. Методы динамизации обеспечивают единообразные способы создания динамических структур данных.
Разложимые задачи поиска
[ редактировать ]Мы определяем проблему поиска предиката совпадение в сете как . Проблема разложимо , если множество можно разбить на подмножества и существует операция унификации результатов такая, что .
Разложение
[ редактировать ]Декомпозиция — это термин, используемый в информатике для разбиения статических структур данных на более мелкие единицы неравного размера. Основной принцип заключается в том, что любое десятичное число можно перевести в представление в любой другой системе счисления. Подробнее о теме см. Декомпозиция (информатика) . Для простоты в этой статье будет использоваться двоичная система, но любую другую систему счисления (а также другие возможности, такие как числа Фибоначчи можно также использовать ).
При использовании двоичной системы набор элементы разбиваются на подмножества размеров с помощью
элементы, где это -й кусочек в двоичном формате. Это означает, что если имеет -й бит равен 0, соответствующий набор не содержит элементов. Каждое из подмножеств имеет то же свойство, что и исходная статическая структура данных. Операции, выполняемые с новой динамической структурой данных, могут включать в себя обход множества, образующиеся в результате декомпозиции. В результате это добавит фактор в отличие от операций со статической структурой данных, но позволит добавить операцию вставки/удаления.
Курт Мельхорн доказал несколько уравнений для временной сложности операций над структурами данных, динамизированными в соответствии с этой идеей. Перечислены некоторые из этих равенств.
Если
- пришло время построить статическую структуру данных
- пришло время запросить статическую структуру данных
- время запроса динамической структуры данных, сформированной в результате декомпозиции
- это амортизированное время вставки
затем
Если является, по крайней мере, полиномиальным , то .
Дальнейшее чтение
[ редактировать ]- Курт Мельхорн, Структуры данных и алгоритмы 3, . Серия EATCS, том. 3, Спрингер, 1984 г.