¿Qué es la complejidad del tiempo polinomial?

Considere cualquier problema en el que el tamaño de entrada esté dado por: [math] n [/ math]

Ahora, si puede resolver este problema, y ​​el tiempo que toma su solución es de la forma [math] O (n ^ c) [/ math], para algunos [math] c \ in \ mathbb {R} [/ math ], entonces dice que la complejidad temporal de esa solución tiene un tamaño polinómico o que básicamente la solución tiene “complejidad temporal polinómica”.

Además, este “tiempo polinomial” no es en sí mismo un término autónomo. Si estás hablando de:

1. Tiempo polinómico determinista: entonces se referirá a la clase de complejidad P.
2. Tiempo polinómico no determinista: básicamente, se referiría a la clase de complejidad NP .
3. Tiempo polinómico aleatorio: entonces la clase de complejidad sería RP .

No entraré en más detalles de las clases referidas (y estoy de acuerdo en que esto sería un saludo). Pero, creo que todo lo que quieres saber era sobre el tiempo polinomial determinista y , por lo tanto, la clase P.

La complejidad del tiempo polinomial es en sí mismo un término importante, ya que en teoría de la complejidad es el punto de referencia de la eficiencia. Entonces, básicamente, si algún problema tiene una solución de tiempo polinomial (determinista), puede decir que el problema se puede resolver de manera eficiente (o en cierto sentido, el problema es fácil de resolver).

El siglo pasado ha visto una revolución absoluta en la forma en que calculamos. Sin embargo, al principio, las cosas no estaban tan claras. Había varias personas escribiendo algoritmos y varias compañías construyendo máquinas de computadora. Ahora, el mismo algoritmo se ejecutaría a diferentes velocidades en diferentes máquinas (debido a las diferencias en la organización de la memoria, las características del transistor, etc.) y se estaba volviendo difícil identificar qué algoritmo usar.
Para resolver este problema, se desarrolló un novedoso sistema de clasificación. Cada algoritmo se desglosaría en pequeños bits de operación, digamos agregando dos números o multiplicando dos números o comparando dos números y luego contaríamos el número de tales operaciones “atómicas” que realizó cada algoritmo. El algoritmo que realizó menos de estas operaciones atómicas se consideró más rápido. Esto fue bueno, ya que eliminó los efectos específicos de la máquina en la velocidad del algoritmo, en cualquier máquina, independientemente de la rapidez con que esa máquina implementara estas operaciones atómicas, el algoritmo que realizaba menos de esas operaciones atómicas siempre ganaría, por lo que no hay ambigüedad. !!!. Esto condujo a la noción de complejidad asintótica del tiempo.
Para aclarar, tomemos un problema simple como la clasificación: hay literalmente docenas de algoritmos para resolver el problema, algunos buenos, otros no tanto. La operación atómica en este problema generalmente se toma como comparación: tomar dos números y compararlos (la mayoría de los algoritmos de clasificación usan tales comparaciones para intercambiar elementos en el orden correcto para avanzar). Supongamos que se nos dan 100 números para ordenar en orden creciente. Luego, un algoritmo como Bubble Sort hará aproximadamente 4950 comparaciones para ordenar los números. Un algoritmo como Merge Sort, por otro lado, solo tomará aproximadamente 665 comparaciones. Claramente, Merge Sort superará a Bubble sort si ambos se ejecutan en la misma máquina.
Si se desea una expresión general para el tiempo de ejecución, resulta que Bubble Sort requiere hasta [math] \ frac {n (n-1)} {2} [/ math] comparaciones para ordenar [math] n [/ math ] números y la combinación de ordenamiento toma [math] n \ log n [/ math] comparaciones para ordenar los mismos números [math] n [/ math].
Cada vez que un algoritmo, en una entrada de tamaño [math] n [/ math], toma como máximo operaciones [math] n ^ c [/ math] para resolver el problema (para algunas constantes fijas [math] c> 0 [/ math] ), se denomina algoritmo de tiempo polinómico o se dice que tiene una complejidad de tiempo polinomial. Para ambos tipos, Bubble y Merge, esta constante puede tomarse como [math] c = 2 [/ math] ya que [math] \ frac {n (n-1)} {2} \ leq n ^ 2 [/ math] así como [math] n \ log n \ leq n ^ 2 [/ math].
Es importante tener en cuenta que el valor [math] c [/ math] debe ser independiente de [math] n [/ math] al hacer esta declaración, es decir, debemos estar seguros de que el algoritmo toma menos de [math] n ^ c [ / math] para todas las entradas de tamaño [math] n [/ math] así como todos los valores de [math] n [/ math] antes de que podamos asignar su complejidad de tiempo.
Hay varios puntos en esta explicación que requieren mayor elaboración: el más notable de ellos es 1) ¿Cuál es el criterio para llamar a algo una operación atómica (por ejemplo, la comparación de dos números en este caso), 2) ¿Cómo definimos el “tamaño”? de la entrada [matemática] n [/ matemática] y 3) ¿Por qué la complejidad del tiempo polinomial es algo interesante para estudiar y apuntar al diseñar algoritmos?

• El algoritmo de ordenamiento por selección en n enteros realiza operaciones An ^ 2 para alguna A constante. Por lo tanto, se ejecuta en el tiempo O (n ^ 2) y es un algoritmo de tiempo polinómico.
• Todas las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) se pueden realizar en tiempo polinómico.
• Las coincidencias máximas en gráficos se pueden encontrar en tiempo polinómico

Por favor vea la complejidad del tiempo. Por ejemplo, si ordena una lista de enteros [matemáticos] n [/ matemáticos] utilizando el algoritmo de clasificación rápida, tomará operaciones [matemática] A {n} ^ {2} [/ matemática], que es un polinomio del tamaño de la lista donde [math] A [/ math] es algo constante. Con la idea de que las operaciones consumen bloques de tiempo aproximadamente iguales, esto significa que el algoritmo de clasificación rápida muestra la complejidad polinómica. Una complejidad de tiempo no polinomial sería aquella que muestra cualquier otro patrón de complejidad. Puede ser lineal, constante, cuadrático, exponencial, cualquier cosa.