Динамизация - Dynamization

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

Разложимые проблемы поиска

Задачу поиска совпадения предиката в множестве определим как . Проблема является разложимой , если множество можно разбить на подмножества и существует операция на результате объединения таких , что . ${\ displaystyle P}$${\ displaystyle M}$${\ 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 ^ {я} * п_ {я}}$

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

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

Если

${\displaystyle P_{S}\left(n\right)\,\!}$ = time to build the static data structure
${\displaystyle Q_{S}\left(n\right)\,\!}$ = time to query the static data structure
${\displaystyle Q_{D}\left(n\right)\,\!}$ = time to query the dynamic data structure formed by decomposition
${\displaystyle {\overline {I}}}$ = amortized insertion time

затем

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

Если хотя бы полиномиальный , то . ${\ Displaystyle Q_ {S} \ влево (п \ вправо)}$${\ Displaystyle Q_ {D} \ влево (п \ вправо) = О \ влево (Q_ {S} \ влево (п \ вправо) \ вправо)}$

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

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