Динамизация

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

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

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

Если используется двоичная система, набор из $n\; \{\backslash \; displaystyle\; n\}$элементов разбивается на подмножества размеров с

$2\; i\; \ast \; ni\; \{\backslash \; displaystyle\; 2\; ^\; \{i\}\; *\; n\_\; \{i\}\}$

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

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

Если

$PS\; (n)\; \{\backslash \; displaystyle\; P\_\; \{S\}\; \backslash \; left\; (n\; \backslash \; right)\; \backslash ,\; \backslash !\}$= время для построения статической структуры данных $QS\; (n)\; \{\backslash \; displaystyle\; Q\_\; \{S\}\; \backslash \; left\; (n\; \backslash \; right)\; \backslash ,\; \backslash !\}$= время для запроса статической структуры данных $QD\; (n)\; \{\backslash \; displaystyle\; Q\_\; \{D\; \}\; \backslash \; left\; (n\; \backslash \; right)\; \backslash ,\; \backslash !\}$= время для запроса динамической структуры данных, сформированной разложением $I\; ¯\; \{\backslash \; displaystyle\; \{\backslash \; overline\; \{I\}\}\}$= амортизированное время вставки

, затем

$QD\; (n)\; =\; O\; (QS\; (n)\; log\; \; (n))\; \{\backslash \; displaystyle\; Q\_\; \{D\}\; \backslash \; left\; (n\; \backslash \; right)\; =\; O\; (\; Q\_\; \{S\}\; \backslash \; left\; (n\; \backslash \; right)\; \backslash \; log\; \backslash \; left\; (n\; \backslash \; right))\; \backslash ,\; \backslash !\}$$I\; ¯\; =\; O\; ((PS\; (n)\; /\; n)\; log\; \; (n))\; \{\backslash \; displaystyle\; \{\backslash \; overline\; \{I\}\}\; =\; O\; (\backslash \; left\; (P\_\; \{S\}\; \backslash \; left\; (n\; \backslash \; right)\; /\; n\; \backslash \; right)\; \backslash \; log\; \backslash \; left\; (n\; \backslash \; right))\}$

Если $QS\; (\; n)\; \{\backslash \; displaystyle\; Q\_\; \{S\}\; \backslash \; left\; (n\; \backslash \; right)\}$не менее многочлен, тогда $QD\; (n)\; =\; O\; (QS\; (n))\; \{\backslash \; displaystyle\; Q\_\; \{D\}\; \backslash \; left\; (n\; \backslash \; right)\; =\; O\; \backslash \; left\; (Q\_\; \{S\}\; \backslash \; left\; (n\; \backslash \; right)\; \backslash \; right)\}$.

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