Динамизация

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

Разложимые задачи поиска

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

Разложение

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

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

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

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

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

Если

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

затем

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

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

Дальнейшее чтение

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