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

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

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