Оценка сложности и ресурсоёмкости алгоритма (введение)
Сложность-формула vs. сложность-число
- Потребление памяти
- Рост числа операций с ростом числа входных данных и качество алгоритма
- константа
- логарифмический
- линейный
- полиномиальный
- экспоненциальный
- факториал и больше (не бывает)
- Пример: оценка сложности простого и бинарного поиска символа в строке
- Пример: оценка сложности построителя беспроигрышной таблицы для крестиков-ноликов
Домашнее задание
почитать статью на Хабре про оценку сложности программы (примере на Питоне!) - Доделать предыдущее домашнее задание. Советы по решателю:
Для простоты работы представлять поле в виде строки из 9 символов (например, "...XO.O.X" — это поле такого вида:
... XO. O.X
- Рекурсивно построить таблицу достижимости игровых состояний в зависимости от того, чей ход первый:
из состояния "........." достижимы 9 состояний: "X........", ".X......." … "........X" (первый ход X)
- из каждого из этих состояний достижимо ещё 8 (второй ход O)
- …
- В список достижимых состояний включать:
- Если наш ход — только наилучшие
- Если чужой ход — все
- В процессе игры обходить таблицу
Решение домашнего задания без PyGame:
Протокол XO: xoproto.py
ИИ: xoai.py
Сетевой сервер: xonet.py
Условные обозначения
— тема по Linux 
— тема повышенной сложности - — теоретическое задание
— тема для самостоятельного изучения