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

671

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

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