Динамизация

В этой статье не указаны источники . Пожалуйста, помогите улучшить эту статью , добавив ссылки на надежные источники . Материалы без ссылок могут быть оспорены и удалены . Найти источники:  «Динамизация» – новости  · газеты  · книги  · ученый  · JSTOR ( февраль 2023 г. ) ( Узнайте, как и когда удалять это сообщение )

В информатике динамизация — это процесс преобразования статической структуры данных в динамическую. Хотя статические структуры данных могут обеспечивать очень хорошую функциональность и быстрые запросы, их полезность ограничена из-за их неспособности быстро расти/сжиматься, что делает их неприменимыми для решения динамических задач , где входные данные изменяются. Методы динамизации предоставляют единообразные способы создания динамических структур данных.

Определим задачу поиска соответствия предиката в наборе как . Задача является разложимой, если набор можно разложить на подмножества и существует операция объединения результатов такая, что .${\displaystyle P}$${\displaystyle М}$${\displaystyle S}$${\displaystyle P(M,S)}$${\displaystyle P}$${\displaystyle S}$${\displaystyle S_{i}}$${\displaystyle +}$${\displaystyle P(M,S)=P(M,S_{0})+P(M,S_{1})+\dots +P(M,S_{n})}$

Разложение — это термин, используемый в информатике для разбиения статических структур данных на более мелкие единицы неравного размера. Основной принцип заключается в идее, что любое десятичное число может быть переведено в представление в любой другой системе счисления. Для получения более подробной информации по теме см. Разложение (компьютерная наука) . Для простоты в этой статье будет использоваться двоичная система счисления, но также может использоваться любая другая система счисления (а также другие возможности, такие как числа Фибоначчи ).

При использовании двоичной системы набор элементов разбивается на подмножества размеров ${\displaystyle n}$

${\displaystyle 2^{i}*n_{i}}$

элементы, где - -й бит в двоичном формате. Это означает, что если -й бит равен 0, соответствующий набор не содержит элементов. Каждый из подмножеств имеет то же свойство, что и исходная статическая структура данных. Операции, выполняемые над новой динамической структурой данных, могут включать обход наборов, сформированных путем декомпозиции. В результате это добавит фактор в отличие от операций со статической структурой данных, но позволит добавить операцию вставки/удаления. ${\displaystyle n_{i}}$${\displaystyle я}$${\displaystyle n}$${\displaystyle n}$${\displaystyle я}$${\displaystyle \log _{2}\left(n\right)}$${\displaystyle O(\log \left(n\right))}$

Курт Мельхорн доказал несколько уравнений для временной сложности операций над структурами данных, динамизированных в соответствии с этой идеей. Некоторые из этих равенств перечислены.

Если

• ${\displaystyle P_{S}\left(n\right)}$пришло время построить статическую структуру данных
• ${\displaystyle Q_{S}\left(n\right)}$пришло время запросить статическую структуру данных
• ${\displaystyle Q_{D}\left(n\right)}$пришло время запросить динамическую структуру данных, сформированную путем декомпозиции
• ${\displaystyle {\overline {Я}}}$амортизированное время вставки

затем

• ${\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\cdot \log \left(n\right)\right)}$
• ${\displaystyle {\overline {I}}=O\left(\left(P_{S}\left(n\right)/n\right)\cdot \log \left(n\right)\right).}$

Если является по крайней мере полиномом , то .${\displaystyle Q_{S}\left(n\right)}$${\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\right)}$

• Курт Мельхорн, Структуры данных и алгоритмы 3, . Серия EATCS, т. 3, Springer, 1984.