Теория отвечает на вопрос «как растёт время при росте n?», а измерение показывает конкретное время на конкретной машине. Хороший инженер соединяет оба: выводит ожидание из анализа и проверяет замером. В этом уроке мы построим небольшие инструменты для эмпирической проверки сложности.
Протокол измерения
- Выберите размеры
nи удваивайте их:n, 2n, 4n, .... - Готовьте входные данные вне таймера.
- Для каждого размера повторяйте несколько раз и берите минимум: он наименее шумный.
- Посчитайте отношение
T(2n) / T(n)или наклон в log-log масштабе. - Сравните результат с теоретическим ожиданием.
| Сложность | Ожидаемое T(2n) / T(n) | наклон в log-log |
|---|---|---|
O(1) | ≈ 1 | 0 |
O(log n) | ≈ 1 (чуть больше) | ≈ 0 |
O(n) | 2 | 1 |
O(n log n) | чуть больше 2 | чуть больше 1 |
O(n^2) | 4 | 2 |
O(n^3) | 8 | 3 |
O(2^n) | T(n + 1) / T(n) = 2 | не прямая |
Функция-бенчмарк и отношения
bench возвращает лучший из повторов. ratio показывает, во сколько раз растёт время при удвоении размера. Результаты зависят от машины, поэтому мы проверяем ответ не точными секундами, а диапазоном.
import random
from time import perf_counter