La mejor respuesta
Google es tu amigo: de Complejidad del tiempo – Wikipedia
Tiempo polinomial
Se dice que un algoritmo es de tiempo polinomial si su tiempo de ejecución es delimitado superior por una expresión polinomial en el tamaño de la entrada para el algoritmo, es decir, T ( n ) = {\ displaystyle O (n ^ {k})} para alguna constante positiva k .
Los problemas para los que existe un algoritmo de tiempo polinomial determinista pertenecen a la clase de complejidad P , que es fundamental en el campo de la teoría de la complejidad computacional . La tesis de Cobham establece que el tiempo polinomial es sinónimo de «manejable», «factible», «eficiente» o «rápido».
Algunos ejemplos de algoritmos de tiempo polinomial:
- El algoritmo de clasificación selección en n enteros realiza {\ displaystyle An ^ {2}} operaciones para algunas A constantes. Por lo tanto, se ejecuta en el tiempo {\ displaystyle O (n ^ {2})} y es un algoritmo de tiempo polinomial.
- Todas las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) se pueden realizar en tiempo polinomial.
- Las coincidencias máximas en gráficos se pueden encontrar en tiempo polinomial.
Podría sugerir tomar algunos cursos tradicionales de informática, como algoritmos utilizando un texto como Introducción a los algoritmos ( también conocido como CLRS) incluso un curso simple de estructuras de datos como el descrito en el paper Un curso de informática fundamental que unifica la teoría y la práctica que utiliza el texto clásico de Wulf, Shaw, Hilfinger y Flon Estructuras fundamentales de la informática .
Respuesta
Si dividimos un polinomio p (x) por algún polinomio d (x) entonces estamos encontrando un cociente q (x) tal que p (x) = d (x) q (x) + r (x) donde r (x) es nuestro resto.
Supongamos que r (x) tuviera un grado ≥︎ n, entonces podríamos haber modificado más dado que d (x) es el grado n hasta nuestro nuevo r (x) ^ {*} tenía un grado estrictamente menor que d (x)
Digamos que tenemos p (x) = x ^ 4 + 1 y d (x) = x ^ 2:
x ^ 4 + 1 = x ^ 2q (x) + r (x)
claramente q (x) = x ^ 2
x ^ 4 + 1 = x ^ 2 \ cdot {x ^ 2} + r (x) ⇒︎ r (x) = 1
Ahora podría seguir adelante e intentar decir que q (x) = x y g et:
x ^ 4 + 1 = {x \ cdot {x}} ^ 2+ (x ^ 4-x ^ 3 + 1)
r (x) = x ^ 4-x ^ 3 + 1?
¡Pero esto no es lo que queremos en absoluto!
Esto es análogo a la división / resto en números enteros:
p = dq + r
7 = 2 \ cdot {3} +1 es correcto
7 = 1 \ cdot {3} +4 no es deseable ya que no dividimos completamente a través de nuestro divisor y dejó una r más grande de lo que deberíamos tener.
El mismo concepto se aplica a los polinomios, pero el grado dicta cuando termines:
\ text {deg} r ( x) text {deg} d (x)
o no redujo completamente el resto al elemento de grado más bajo en la clase de equivalencia módulo d (x), o en términos menos matemáticos, puede en realidad, encuentre una clase completa de polinomios equivalentes cuando modifique por un polinomio dado, pero desea el más pequeño con un grado pellizcado entre 0 y n-1 (incluidos esos extremos) como resto.
10 = 7 = 4 = 1 ~ \ text {mod} 3 ¡pero solo uno es un caso de resto válido para la división larga entera!
x ^ 4 + 1 = x ^ 2 + 1 = 1 ~ \ text {mod } x ^ 2 pero solo uno es un caso de resto válido para la división larga polinomial.
Entonces
\ text {deg} r (x) text {deg} d (x)