lunes 24 de agosto · 13:00–14:15 · en 2 días
CN122 · lunes 24/08/2026 · 13:00-14:15 · Sesión 5
Polinomios representados con arreglos
La densa es simple y da acceso O(1) al coeficiente de cualquier grado, pero desperdicia espacio si el polinomio tiene huecos. Para x¹⁰⁰⁰ + 1 se necesitan mil una celdas para guardar dos términos.
La dispersa ahorra memoria pero exige recorrer para encontrar un exponente. La decisión depende de la densidad esperada, y esa es exactamente la clase de decisión que enseña este curso.
En representación densa es trivial: se suman elemento a elemento hasta el grado mayor. En dispersa se recorren ambos en paralelo comparando exponentes, como la mezcla de dos listas ordenadas.
Cada término del primero multiplica a cada término del segundo, con los exponentes sumándose: O(n·m). El resultado tiene grado igual a la suma de los grados, así que el arreglo destino debe dimensionarse antes.
Evaluar directamente cuesta O(n²) por las potencias. Horner reescribe p(x) = a₀ + x(a₁ + x(a₂ + …)) y evalúa en O(n) con una sola multiplicación y una suma por término.
Es el mismo polinomio y el mismo resultado; solo cambió el orden de las operaciones. Vale la pena verlo como ejemplo de que reorganizar un cálculo puede mejorar su complejidad.
Implementar suma, multiplicación y evaluación con Horner en ambas representaciones.
Nada anotado en esta sesión todavía.