Jump to content

Динамизация

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

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

[ редактировать ]

Мы определяем проблему поиска предиката совпадение в сете как . Проблема разложимо , если множество можно разбить на подмножества и существует операция унификации результатов такая, что .

Разложение

[ редактировать ]

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

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

элементы, где это -й кусочек в двоичном формате. Это означает, что если имеет -й бит равен 0, соответствующий набор не содержит элементов. Каждое из подмножеств имеет то же свойство, что и исходная статическая структура данных. Операции, выполняемые с новой динамической структурой данных, могут включать в себя обход множества, образующиеся в результате декомпозиции. В результате это добавит фактор в отличие от операций со статической структурой данных, но позволит добавить операцию вставки/удаления.

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

Если

  • пришло время построить статическую структуру данных
  • пришло время запросить статическую структуру данных
  • время запроса динамической структуры данных, сформированной в результате декомпозиции
  • это амортизированное время вставки

затем

Если является, по крайней мере, полиномиальным , то .

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

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: eef023583e68b637eb7b09cfdea3a0f3__1676164200
URL1:https://arc.ask3.ru/arc/aa/ee/f3/eef023583e68b637eb7b09cfdea3a0f3.html
Заголовок, (Title) документа по адресу, URL1:
Dynamization - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)