# Сложность и организация вычислений ## Зачем оценивать сложность Корректный алгоритм может быть практически бесполезен, если время или память растут слишком быстро. Анализ сложности отвечает не на вопрос «сколько секунд», а на вопрос «как изменится потребление ресурсов при росте входа». Для данных будем использовать: - \(n\) — число объектов; - \(d\) — число признаков; - \(k\) — число классов или компонент; - \(T\) — число итераций. ## Асимптотические обозначения \(f(n)=O(g(n))\), если существуют \(c>0\) и \(n_0\), такие что \[ 0\leq f(n)\leq c\,g(n)\quad\text{при }n\geq n_0. \] \(\Omega(g(n))\) задаёт нижнюю границу, а \(\Theta(g(n))\) — одновременно верхнюю и нижнюю с точностью до констант. Например, \[ 3n^2+10n+7=\Theta(n^2), \] потому что при больших \(n\) квадратичный член доминирует. Это не означает, что коэффициенты и младшие члены всегда неважны: для реальных размеров они могут определять более быстрый вариант. ## Типичные скорости роста От более медленного роста к более быстрому: \[ O(1),\quad O(\log n),\quad O(n),\quad O(n\log n),\quad O(n^2),\quad O(2^n). \] Удвоение \(n\) примерно удваивает линейную работу, увеличивает квадратичную в четыре раза и экспоненциальную — радикально. Логарифмическое время возникает, когда каждый шаг уменьшает задачу в постоянное число раз, как бинарный поиск. ## Анализ циклов Последовательные блоки складываются: \[ O(n)+O(n^2)=O(n^2). \] Вложенные независимые циклы перемножаются: ```python total = 0.0 for i in range(n): for j in range(d): total += X[i, j] ``` Выполняется \(nd\) сложений, значит время \(O(nd)\), а дополнительная память \(O(1)\). Не следует автоматически называть это \(O(n^2)\): \(n\) и \(d\) — разные параметры. ## Стоимость линейной алгебры Для \(\mathbf{A}\in\mathbb{R}^{m\times n}\) и \(\mathbf{B}\in\mathbb{R}^{n\times p}\) матричное произведение требует приблизительно \(mnp\) умножений и столько же сложений: \[ \mathbf{C}_{ij}=\sum_{\ell=1}^{n}A_{i\ell}B_{\ell j}, \qquad O(mnp). \] Частные случаи: - матрица-вектор \((n\times d)(d)\): \(O(nd)\); - \(\mathbf{X}^\top\mathbf{X}\): \(O(nd^2)\); - плотное решение системы \(d\times d\): обычно \(O(d^3)\); - хранение \(\mathbf{X}\): \(O(nd)\). Для разреженной матрицы важнее число ненулевых элементов \(\operatorname{nnz}(\mathbf{X})\). Умножение на вектор может стоить \(O(\operatorname{nnz}(\mathbf{X}))\), если формат хранения поддерживает разреженность. ## Пример: линейная регрессия Один полный градиент \[ \nabla L =\frac1n\mathbf{X}^\top(\mathbf{Xw}-\mathbf{y}) \] состоит из: 1. \(\mathbf{Xw}\): \(O(nd)\); 2. вычитания \(\mathbf{y}\): \(O(n)\); 3. умножения \(\mathbf{X}^\top\mathbf{r}\): \(O(nd)\). Итого \(O(nd)\) времени и \(O(n)\) дополнительной памяти для остатка. За \(T\) итераций — \(O(Tnd)\). Нормальные уравнения требуют формирования \(\mathbf{X}^\top\mathbf{X}\) за \(O(nd^2)\) и решения системы примерно за \(O(d^3)\). Какой подход быстрее, зависит от \(n,d,T\), памяти и обусловленности. ## Векторизация: та же асимптотика, другое исполнение ```python import numpy as np rng = np.random.default_rng(0) X = rng.normal(size=(1000, 100)) w = rng.normal(size=100) # Математически это O(nd). y_vectorized = X @ w print(y_vectorized.shape) ``` Цикл Python и `X @ w` имеют одинаковый порядок \(O(nd)\), но векторизованная операция выполняется оптимизированной библиотекой, использует кэш и SIMD, а иногда несколько потоков. Big O не отражает эти константы. Векторизация может увеличить пиковую память из-за временных массивов: ```python # Создаёт временный массив формы X.shape. column_energy = (X**2).sum(axis=0) # Эквивалентное свёртывание без явного X**2 может быть экономнее. column_energy_einsum = np.einsum("ij,ij->j", X, X) print(np.allclose(column_energy, column_energy_einsum)) ``` ## Память и представление данных Массив `float64` из \(nd\) элементов занимает примерно \(8nd\) байт, `float32` — \(4nd\). Для миллиона объектов и тысячи плотных признаков `float64` потребует около \(8\) ГБ только для матрицы. Пиковая память включает: \[ \text{данные}+\text{параметры}+\text{активации} +\text{градиенты}+\text{временные массивы}. \] Срез NumPy часто является представлением без копирования, но fancy indexing обычно создаёт копию. Проверять это можно через `np.shares_memory`. ## Локальность и кэш Доступ к последовательным адресам памяти быстрее случайного доступа. NumPy по умолчанию хранит двумерные массивы построчно в C-порядке. Поэтому обход соседних элементов последней оси обычно лучше использует кэш. Асимптотика двух обходов может совпадать, но фактическое время различаться из-за промахов кэша и пропускной способности памяти. Современное вычисление часто ограничено не числом арифметических операций, а перемещением данных. ## Пакетная обработка Если весь набор не помещается в память устройства, его делят на батчи размера \(b\). Для плотного линейного слоя: \[ \mathbf{H}=\mathbf{X}_{b\times d}\mathbf{W}_{d\times h} \] стоимость одного батча \(O(bdh)\), а активации занимают \(O(bh)\). Уменьшение \(b\) снижает пиковую память, но может хуже загружать устройство и увеличивать накладные расходы. Градиент по мини-батчу также более шумный. ## Амортизированная сложность Одна операция может иногда быть дорогой, но дешёвой в среднем по последовательности. Добавление в динамический массив обычно \(O(1)\) амортизированно: редкое расширение стоит \(O(n)\), но ёмкость увеличивается геометрически, и общая стоимость \(n\) добавлений остаётся \(O(n)\). Амортизированная оценка не равна средней по случайному входу: она гарантирует стоимость последовательности операций без вероятностной модели входа. ## Время обучения и время предсказания Сложность следует оценивать отдельно: - подготовка данных; - обучение; - предсказание одного объекта и батча; - память модели; - память промежуточных вычислений. Например, \(k\)-NN почти не обучается, но предсказание по плотным данным требует сравнения с \(n\) объектами: \(O(nd)\). Линейная модель дорого оптимизируется, но одно предсказание стоит \(O(d)\). ## Измерение производительности Теоретическая оценка определяет ожидаемый рост, профилирование находит реальное узкое место. Надёжный эксперимент: 1. прогревает код; 2. повторяет измерение; 3. меняет один размер входа; 4. фиксирует версии, dtype и устройство; 5. проверяет корректность сравниваемых результатов. ```python from time import perf_counter start = perf_counter() for _ in range(100): _ = X @ w elapsed = perf_counter() - start print(f"{elapsed / 100:.6e} s per run") ``` Очень короткие операции лучше измерять `timeit`; фоновая нагрузка и многопоточность делают единичный замер ненадёжным. ## Компромиссы - **Время против памяти:** кэширование ускоряет повторные вычисления, но требует памяти. - **Точность против скорости:** `float32` быстрее на многих ускорителях, но имеет меньший диапазон точности. - **Предвычисление против задержки:** индекс строится долго, зато ускоряет запросы. - **Точная задача против приближения:** случайные проекции и выборка уменьшают стоимость ценой контролируемой ошибки. ## Типичные ошибки - Big O не является временем в секундах и не учитывает константы. - Нельзя скрывать разные переменные одним \(n\), если они растут независимо. - Векторизация не меняет автоматически асимптотическую сложность. - Оценка памяти без временных массивов часто занижена. - Средняя, худшая и амортизированная сложности отвечают на разные вопросы. - Более быстрый алгоритм не полезен, если он меняет результат или нарушает численную устойчивость. ## Резюме Сложность описывает масштабирование времени и памяти. Для ML особенно важны \(n,d,k,T\), стоимость матричных операций, плотность данных и пиковая память. Асимптотический анализ выбирает класс решения, а измерения и профилирование уточняют константы и аппаратные ограничения.