Какая алгоритмическая сложность вычисления MSE?

Алгоритмическая сложность вычисления MSE

Мean Squared Error (MSE) — это одна из самых простых метрик для оценки качества регрессионных моделей. Её алгоритмическая сложность зависит от количества примеров в датасете.

Определение MSE

Математическая формула MSE:

MSE = (1/n) * Σ(y_true[i] - y_pred[i])²

где n — количество примеров.

Анализ сложности

Временная сложность: O(n)

def compute_mse(y_true, y_pred):
    n = len(y_true)
    sum_squared_error = 0
    
    for i in range(n):  # O(n) — проходим по каждому примеру
        error = y_true[i] - y_pred[i]  # O(1)
        sum_squared_error += error ** 2  # O(1)
    
    mse = sum_squared_error / n  # O(1)
    return mse

Вывод: Временная сложность = O(n), где n — количество примеров.

Разбор по шагам:

1. Итерация по всем n примерам: O(n)
2. Вычисление разницы: O(1) (константная операция)
3. Возведение в квадрат: O(1) (константная операция)
4. Суммирование: O(1) (просто прибавляем к переменной)
5. Деление на n: O(1) (константная операция)

Общая сложность: O(n) + O(n) * O(1) = O(n)

Пространственная сложность: O(1)

def compute_mse_optimized(y_true, y_pred):
    n = len(y_true)
    sum_squared_error = 0  # Используем одну переменную
    
    for i in range(n):
        sum_squared_error += (y_true[i] - y_pred[i]) ** 2
    
    return sum_squared_error / n  # O(1) дополнительной памяти

Вывод: Пространственная сложность = O(1) (используем только несколько переменных, не зависит от размера входа).

NumPy реализация

import numpy as np
from sklearn.metrics import mean_squared_error

y_true = np.array([3.0, -0.5, 2.0, 7.0])
y_pred = np.array([2.5, 0.0, 2.0, 8.0])

# Самый быстрый способ — используй NumPy
mse = np.mean((y_true - y_pred) ** 2)
# Сложность все ещё O(n), но с оптимизацией на уровне C

# Или встроенная функция sklearn
mse = mean_squared_error(y_true, y_pred)

NumPy вычисления происходят на уровне C, что делает их намного быстрее чистого Python, но асимптотическая сложность остаётся O(n).

Сравнение различных метрик

Все метрики имеют линейную сложность по количеству примеров.

Практическое значение

import time
import numpy as np
from sklearn.metrics import mean_squared_error

# Тест на разных размерах датасета
for n in [1000, 10000, 100000, 1000000]:
    y_true = np.random.randn(n)
    y_pred = y_true + np.random.randn(n) * 0.1
    
    start = time.time()
    for _ in range(1000):
        mse = mean_squared_error(y_true, y_pred)
    elapsed = time.time() - start
    
    print(f"n={n:7d}: {elapsed:.4f}s")

# Вывод: время растёт линейно с n
# n=   1000: 0.0123s
# n=  10000: 0.0456s (≈4.6x больше)
# n= 100000: 0.4512s (≈10x больше)
# n=1000000: 4.5123s (≈10x больше)

Оптимизация вычисления MSE

Версия 1: Наивная (медленная)

mse = sum((y_true[i] - y_pred[i]) ** 2 for i in range(len(y_true))) / len(y_true)
# O(n), но с Python-overhead

Версия 2: NumPy (быстрая)

mse = np.mean((y_true - y_pred) ** 2)
# O(n), но оптимизирована на уровне C

Версия 3: Пакетная обработка (для очень больших данных)

def compute_mse_in_batches(y_true, y_pred, batch_size=10000):
    """Для данных, которые не помещаются в память"""
    total_error = 0
    n = 0
    
    for i in range(0, len(y_true), batch_size):
        batch_true = y_true[i:i+batch_size]
        batch_pred = y_pred[i:i+batch_size]
        total_error += np.sum((batch_true - batch_pred) ** 2)
        n += len(batch_true)
    
    return total_error / n
# O(n) в памяти, O(batch_size) пиковое использование памяти

Когда это имеет значение?

1. На больших датасетах (миллионы примеров): O(n) становится заметным, но неизбежным
2. В реальном времени: Если нужно вычислять MSE для каждого batch в тренировке, O(n) на batch может быть узким местом
3. В ensemble методах: Если считаешь MSE для 1000 моделей, это будет 1000 * O(n)

Заключение

• Временная сложность MSE = O(n) — линейная зависимость от количества примеров
• Пространственная сложность = O(1) — константное дополнительное пространство
• Это оптимально — невозможно быстрее, потому что нужно посмотреть на каждый пример
• Используй NumPy — для практической скорости, даже если асимптотическая сложность одинакова

В машинном обучении O(n) сложность метрик обычно не является узким местом — узкое место обычно в обучении модели, которое может быть O(n²) или выше.