Алгоритмы и структуры данных поиска: Сложность и модели вычислений. Анализ учетных стоимостей. Часть 2. Бабенко Максим

Во второй части лекции Бабенко Максим продолжил рассказ обо всех сложностях и моделях вычисления, а также об анализе учетных стоимостей.

1. Анализ учетных стоимостей операций: функция потенциала, истинные и учетные стоимости.
2. Стеки и очереди.
3. Реализация на основе массива переменного размера и на основе связанного списка.
4. Моделирование очереди с помощью двух стеков.
5. Задача о поддержании динамического максимума в стеке и очереди.
6. Изменяемые (mutable) и неизменяемые (immutable) структуры данных.
7. Структуры данных с хранением истории (persistent).
8. Immutable-стек и immutable-очередь.
9. Проблема множественного будущего при анализе учетных стоимостей в persistent-структурах.