Оглавление
Динамизация
-
Динамизация в информатике
- Динамизация – это процесс преобразования статических структур данных в динамические.
- Статические структуры данных имеют ограниченную функциональность и не могут быстро увеличиваться или уменьшаться.
- Методы динамизации обеспечивают единообразные способы создания динамических структур данных.
-
Задачи декомпозируемого поиска
- Проблема поиска предиката в сете может быть разложена на подмножества и объединена для получения результата.
- Декомпозиция – это процесс разбиения статических структур данных на более мелкие единицы.
- Декомпозиция позволяет добавлять операции вставки и удаления, но увеличивает время выполнения операций.
-
Временная сложность операций
- Курт Мельхорн вывел уравнения для временной сложности операций над динамизированными структурами данных.
- Амортизированное время установки и время запроса динамизированной структуры данных зависят от времени создания статической структуры данных и размера входных данных.
- Если время создания статической структуры данных полиномиально, то время запроса динамизированной структуры также полиномиально.