Абстрактный тип данных (ADT)
Предпосылки: базовое программирование (переменные, типы, условия, циклы, функции), оценка сложности в O(…).
Одну и ту же задачу — например, хранить набор элементов — можно решить массивом, списком, деревом. Чтобы сравнивать такие решения, нужен единый язык: какие операции структура поддерживает и с какой сложностью, без привязки к реализации. Этот язык — ADT (Abstract Data Type).
ADT описывает контракт: набор операций и их поведение. Реализация может быть любой, если контракт соблюдён. Это позволяет менять внутреннее устройство структуры, не ломая код, который ею пользуется.
Первое требование, которое можно сформулировать на языке ADT: положить n значений и достать любое по номеру за O(1). Этот контракт — ADT Array, и массив — его простейшая реализация.
Sources
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. (abstract data types, contracts).