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

784

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

  1. Основные ресурсы: память и время.
  2. О-символика.
  3. Примеры моделей вычисления: машина Тьюринга, RAM-машина.
  4. Сложность в среднем и худшем случаях.
  5. Пример: задача сортировки.
  6. Сортировка выбором.
  7. Теоретико-информационная нижняя оценка сложности.
  8. Разрешающие деревья.
  9. Нижняя оценка сложности в модели разрешающих деревьев.
  10. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации.
  11. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.