# ОП.04 · Занятие 04 · Замеры времени и памяти алгоритмов в Python

44 экрана, 90 минут. Продолжение занятия 03: T(n), S(n), O(1), O(n), O(n²).
Содержание и порядок — по приложенной структуре (`SOURCE_STRUCTURE.md`).

## Сценарий

Теория Big O → прогноз → запуск Python → замер → сравнение → объяснение.
До выбора варианта правильные ответы скрыты. В лабораторных блоках студент
записывает и фиксирует прогноз; только после этого доступны поля замеров.
После заполнения таблицы открывается объяснение и поле собственного вывода.
Нулевые значения допустимы (например, после округления), но деление на ноль
не выполняется. Пустые, отрицательные и нечисловые значения не принимаются.

Презентация работает без сборки и внешних библиотек: откройте index.html.
Все Python-эксперименты запускаются **локально**, не в браузере. Распакуйте ZIP
целиком и запускайте команды внутри algorithm_measurements; Python 3.10+.

## Ритм пары

| Минуты | Экраны | Действие |
|---|---|---|
| 0–10 | 1–8 | Связь модели и запуска, первый perf_counter, рост n |
| 10–20 | 9–11 | Разброс реальных повторов, медиана, границы измерения |
| 20–45 | 12–21 | Прогноз и эксперимент для O(1), O(n), O(n²) |
| 45–55 | 22–25 | Два O(n), поиск в list и set |
| 55–70 | 26–32 | Дополнительная память, tracemalloc, список и генератор |
| 70–80 | 33–39 | Компромисс времени и памяти, поиск дубликатов |
| 80–90 | 40–44 | Методика, ошибки, обобщение, чек-лист |

## Управление

- Стрелки ←/→, PageUp/PageDown, кнопки внизу: предыдущий/следующий экран.
- Home/End: первый/последний. F: полноэкранный режим, если браузер разрешает.
- Оглавление: любой из 44 экранов, материалы, экспорт результатов JSON.
- Длинный код разбит на части по 14 непустых строк. Стрелки под кодом
  переключают части; копирование и скачивание всегда берут полный код.
- В полях ввода стрелки работают как обычно и не переключают слайд.
- Прямая ссылка: `index.html#slide-20`.
- Прогнозы, ответы, замеры, выводы и чек-лист сохраняются в localStorage
  текущего браузера. На file:// поддержка хранения зависит от браузера;
  экспортируйте результаты, особенно при работе в приватном окне.
- Для новой группы удобно открыть страницу в отдельном профиле браузера.
- «Запустить ещё раз» на экране 9 сохраняет старую серию в истории экспорта
  и очищает поля для новой. Сам скрипт студент повторяет в терминале.

## Файлы

Основной комплект: measurements.py и 01–10 из исходной структуры.
Дополнения 11–14: два суммирования, сравнение памяти, список/генератор,
семь реальных повторов. В скачиваемых файлах добавлены импорты и точки
запуска; показанные фрагменты исходного задания сохранены.

Исходные иллюстративные секунды заменены вопросительными знаками/пустыми
полями: никаких заранее заполненных benchmark-значений или случайных
«замеров». Для экрана 9 используется настоящий Python-скрипт.
Модели 1, n, n² подписаны как условный объём работы. Графики результатов
строятся только из пользовательских значений на линейных осях.

## Что проговорить

- Один замер не устанавливает Big O; анализ кода необходим.
- У очень быстрых операций таймер/вызов функции могут доминировать.
  Повторы одиночных вызовов не устраняют накладные расходы. Для углубления
  пригоден timeit с пакетами операций и делением на их число.
- O(1) поиска в set — ожидаемая оценка, худшая O(n). Построение set имеет
  свою стоимость; для большого числа запросов она может окупиться.
- O(1) дополнительной памяти поиска в готовом set не означает, что само
  множество бесплатно: структура занимает O(n).
- Деление байтов на 1024² даёт MiB. В исходных Python-примерах оставлена
  подпись MB; интерфейс уточняет единицу.
- tracemalloc отслеживает выделения Python, не весь RSS процесса.
  Время и память измеряются отдельно, чтобы трассировка не влияла на таймер.
- Оценки арифметики используют учебную модель постоянного размера числа.
  Python int может расти по числу бит: S(n) = O(1) здесь описывает отсутствие
  структуры из n чисел, а не буквальную неизменность всех байтов.

## Артефакт студента

Экспорт JSON: первоначальные прогнозы, подписи строк/единицы, собственные
замеры, история повторной серии, выводы и чек-лист. Устно объяснить различие
nested и set по двум ресурсам, опираясь на анализ и собственный эксперимент.