Problema
La regresión lineal encuentra la recta y = slope × x + intercept que mejor se ajusta a los datos, es decir, la que minimiza la suma de los errores al cuadrado. Para una sola variable de entrada hay una fórmula exacta:
- slope = Σ(x - x̄)(y - ȳ) / Σ(x - x̄)²
- intercept = ȳ - slope × x̄
donde x̄ e ȳ son las medias de xs e ys. Si todos los xs son iguales, devuelve slope 0 e intercept ȳ.
Implementa linear_regression(xs, ys).
Entrada
xs, ys: Los valores x e y de los puntos (misma longitud).
Salida
Devuelve [slope, intercept].
Restricciones
1 ≤ número de puntos ≤ 10 000
-10 000 ≤ cada valor ≤ 10 000
Ejemplos
Entrada:
xs = [1.0, 2.0, 3.0, 4.0]
ys = [3.0, 5.0, 7.0, 9.0]
Salida esperada:
expected = [2.0, 1.0]
Entrada:
std::vector<double> xs = {1.0, 2.0, 3.0, 4.0};
std::vector<double> ys = {3.0, 5.0, 7.0, 9.0};
Salida esperada:
std::vector<double> expected = {2.0, 1.0};
Entrada:
double[] xs = new double[] {1.0, 2.0, 3.0, 4.0};
double[] ys = new double[] {3.0, 5.0, 7.0, 9.0};
Salida esperada:
double[] expected = new double[] {2.0, 1.0};
Explicación
Los puntos están exactamente sobre y = 2x + 1. x̄ = 2.5, ȳ = 6, Σ(x - x̄)(y - ȳ) = 10 y Σ(x - x̄)² = 5, así que slope = 2 e intercept = 6 - 2 × 2.5 = 1.
Entrada:
xs = [0.0, 1.0, 2.0]
ys = [1.0, 3.0, 2.0]
Salida esperada:
expected = [0.5, 1.5]
Entrada:
std::vector<double> xs = {0.0, 1.0, 2.0};
std::vector<double> ys = {1.0, 3.0, 2.0};
Salida esperada:
std::vector<double> expected = {0.5, 1.5};
Entrada:
double[] xs = new double[] {0.0, 1.0, 2.0};
double[] ys = new double[] {1.0, 3.0, 2.0};
Salida esperada:
double[] expected = new double[] {0.5, 1.5};
Explicación
x̄ = 1 e ȳ = 2. Σ(x - x̄)(y - ȳ) = (-1)(-1) + 0 + (1)(0) = 1 y Σ(x - x̄)² = 2, así que slope = 0.5 e intercept = 2 - 0.5 × 1 = 1.5.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
La mejor recta se obtiene a partir de cómo x e y varían juntos alrededor de sus medias.
Pista 2
Calcula primero las medias y luego acumula el numerador y el denominador de la fórmula de la pendiente.
Pista 3
Si todos los valores de x son iguales, la pendiente es indefinida, así que devuelve una recta horizontal en la media de y.
Complejidad esperada
tiempo O(n), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.