Complejidad computacional

La complejidad computacional es un concepto en informática y la teoría de algoritmos , que denota una función de la dependencia de la cantidad de trabajo que realiza algún algoritmo en el tamaño de los datos de entrada. La rama que estudia la complejidad computacional se denomina teoría de la complejidad computacional . La cantidad de trabajo se suele medir en términos de conceptos abstractos de tiempo y espacio denominados recursos informáticos . El tiempo está determinado por el número de pasos elementales necesarios para resolver el problema, mientras que el espacio está determinado por la cantidad de memoria o espacio en el medio de almacenamiento.. Así, en esta área se intenta responder a la pregunta central del desarrollo de algoritmos: “¿cómo cambiará el tiempo de ejecución y la cantidad de memoria ocupada dependiendo del tamaño de la entrada?”. Aquí, el tamaño de la entrada es la longitud de la descripción de los datos del problema en bits (por ejemplo, en el problema del viajante de comercio, la longitud de la entrada es casi proporcional al número de ciudades y carreteras entre ellas), y el el tamaño de la salida es la longitud de la descripción de la solución al problema (la mejor ruta en el problema del viajante de comercio).

En particular, la teoría de la complejidad computacional define problemas NP-completos que una máquina de Turing no determinista puede resolver en tiempo polinomial , mientras que no se conoce ningún algoritmo polinomial para una máquina de Turing determinista . Por lo general, estos son problemas de optimización complejos , por ejemplo, el problema del viajante de comercio .

Estrechamente relacionadas con la informática teórica se encuentran áreas como el análisis de algoritmos y la teoría de la computabilidad . El vínculo entre la informática teórica y el análisis algorítmico es el hecho de que su formación está dedicada al análisis de la cantidad requerida de recursos de ciertos algoritmos para resolver problemas, mientras que una cuestión más general es la posibilidad de utilizar algoritmos para tales problemas. Para ser específicos, intentaremos clasificar los problemas que pueden o no resolverse con recursos limitados. Una fuerte limitación de los recursos disponibles distingue la teoría de la complejidad computacional de la teoría computacional, esta última responde a la pregunta de qué problemas, en principio, se pueden resolver algorítmicamente.

Complejidad de tiempo y espacio

La teoría de la complejidad computacional surgió de la necesidad de comparar la velocidad de los algoritmos, describir claramente su comportamiento (tiempo de ejecución y cantidad de memoria requerida) dependiendo del tamaño de la entrada.

El número de operaciones elementales gastadas por el algoritmo para resolver una instancia particular del problema depende no solo del tamaño de los datos de entrada, sino también de los datos mismos. Por ejemplo, el número de operaciones del algoritmo de ordenación por inserción es mucho menor si los datos de entrada ya están ordenados. Para evitar tales dificultades, considere el concepto de complejidad temporal del algoritmo en el peor de los casos .

La complejidad temporal de un algoritmo (en el peor de los casos) es una función del tamaño de los datos de entrada, igual al número máximo de operaciones elementales realizadas por el algoritmo para resolver una instancia de problema del tamaño especificado.

De manera similar al concepto de complejidad temporal en el peor de los casos , se define el concepto de complejidad temporal de un algoritmo en el mejor de los casos . También consideran el concepto de tiempo medio de ejecución del algoritmo , es decir, la expectativa matemática del tiempo de ejecución del algoritmo. A veces se dice simplemente: " La complejidad temporal del algoritmo " o " El tiempo de ejecución del algoritmo ", refiriéndose a la complejidad temporal del algoritmo en el peor, mejor o promedio de los casos (según el contexto).

Por analogía con la complejidad del tiempo, determinan la complejidad espacial del algoritmo , solo que aquí no hablan de la cantidad de operaciones elementales, sino de la cantidad de memoria utilizada.

Complejidad asintótica

A pesar de que la función de complejidad temporal de un algoritmo puede determinarse exactamente en algunos casos, en la mayoría de los casos no tiene sentido buscar su valor exacto. El hecho es que, en primer lugar, el valor exacto de la complejidad del tiempo depende de la definición de las operaciones elementales (por ejemplo, la complejidad se puede medir en el número de operaciones aritméticas , operaciones de bits u operaciones en una máquina de Turing ), y en segundo lugar, como el tamaño de los datos de entrada aumenta, la contribución de los factores constantes y los términos de orden inferior que aparecen en la expresión para el tiempo de funcionamiento exacto se vuelve extremadamente insignificante.

La consideración de grandes datos de entrada y la estimación del orden de crecimiento del tiempo de ejecución del algoritmo conduce al concepto de la complejidad asintótica del algoritmo. Al mismo tiempo, un algoritmo con menor complejidad asintótica es más eficiente para todos los datos de entrada, excepto, posiblemente, para datos de pequeño tamaño. La notación asintótica se utiliza para escribir la complejidad asintótica de los algoritmos :

Designacion	Explicación intuitiva	Definición
$f(n)\en O(g(n))$	$F$ está acotado superiormente por una función (hasta un factor constante) asintóticamente $gramo$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\leq \|Cg(n)\|$ o $\existe (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)$
$f(n)\en \Omega (g(n))$	$F$ está acotado desde abajo por una función (hasta un factor constante) asintóticamente $gramo$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|$
$f(n)\en \Theta (g(n))$	$F$ acotado por abajo y por arriba por la función asintóticamente $gramo$	$\existe (C,C'>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|\leq \|C' g(n)\|$
$f(n)\en o(g(n))$	$gramo$ domina asintóticamente $F$	$\forall (C>0),\existe n_{0}:\forall (n>n_{0})\;\|f(n)\|<\|Cg(n)\|$
$f(n)\en \omega (g(n))$	$F$ domina asintóticamente $gramo$	$\forall (C>0),\existe n_{0}:\forall (n>n_{0})\;\|Cg(n)\|<\|f(n)\|$
${\ estilo de visualización f (n) \ sim g (n)}$	$F$ es equivalente asintóticamente $gramo$	$\lim _{n\to\infty}{\frac {f(n)}{g(n)}}=1$

Ejemplos

“aspirar una alfombra” lleva un tiempo linealmente dependiente de su área ( ), es decir, una alfombra con el doble de área tardará el doble. En consecuencia, con un aumento en el área de la alfombra en cien mil veces, el volumen de trabajo aumenta estrictamente proporcionalmente en cien mil veces, etc. $\ Theta (A)$
"Encontrar un nombre en la guía telefónica" solo lleva tiempo, logarítmicamente dependiente del número de entradas ( ), porque al abrir la guía aproximadamente por la mitad, reducimos el tamaño del "problema pendiente" a la mitad (ordenando los nombres alfabéticamente). Así, en un libro con un volumen de 1000 páginas, cualquier nombre no se encuentra más que a la vez (aperturas de libros). Al aumentar el volumen de páginas a cien mil, el problema se sigue solucionando en visitas. (Ver búsqueda binaria ). $O(\log_{2}(n))$ $\ log _ {2} 1000 \ aproximadamente 10$ $\ log _ {2} 100000 \ aproximadamente 17$

Notas

Dado que , en la estimación de complejidad asintótica, el "logaritmo" a menudo se escribe sin mencionar la base, por ejemplo, . $\log _{a}b={\frac {\log _{c}b}{\log _{c}a))$ $O(n\log n)$

Debe enfatizarse que la tasa de crecimiento del tiempo de ejecución en el peor de los casos no es el único ni el criterio más importante para evaluar algoritmos y programas. Aquí hay algunas consideraciones que le permiten ver el criterio de tiempo de ejecución desde otros puntos de vista:

Si el programa que se está creando se usará solo unas pocas veces, entonces el costo de escribir y depurar el programa dominará el costo total del programa, es decir, el tiempo de ejecución real no tendrá un impacto significativo en el costo total. En este caso, se debe preferir el algoritmo que sea más simple de implementar.

Si el programa funcionará solo con datos de entrada "pequeños", entonces la tasa de crecimiento del tiempo de ejecución será menos importante que la constante presente en la fórmula del tiempo de ejecución [1] . Al mismo tiempo, el concepto de "pequeñez" de los datos de entrada también depende del tiempo de ejecución exacto de los algoritmos de la competencia. Hay algoritmos, como el algoritmo de multiplicación de enteros , que son asintóticamente los más eficientes, pero que nunca se utilizan en la práctica, ni siquiera para problemas grandes, porque sus constantes de proporcionalidad son muy superiores a las de otros más simples y menos "eficientes". algoritmos Otro ejemplo son los montones de Fibonacci , a pesar de su eficiencia asintótica, desde un punto de vista práctico, la complejidad del software de implementación y los grandes valores de constantes en las fórmulas de tiempo de ejecución los hacen menos atractivos que los árboles binarios ordinarios [1] .

Si la solución de algún problema para un grafo de n-vértices con un algoritmo lleva un tiempo (número de pasos) del orden de n C , y con otro - del orden de n+n!/C, donde C es un número constante , entonces de acuerdo con la "ideología polinomial" el primer algoritmo es prácticamente eficiente y el segundo no lo es, aunque, por ejemplo, en C=10 (10 10 ) la situación es todo lo contrario [2] .A. A. Zykov

Hay casos en que los algoritmos eficientes requieren cantidades tan grandes de memoria de la máquina (sin posibilidad de utilizar medios de almacenamiento externos) que este factor anula la ventaja de la "eficiencia" del algoritmo. Por lo tanto, no solo es importante la "complejidad del tiempo", sino también la "complejidad de la memoria" (complejidad espacial).

En los algoritmos numéricos, la precisión y la estabilidad de los algoritmos no son menos importantes que su eficiencia en el tiempo.

Clases de dificultad

Una clase de complejidad es un conjunto de problemas de reconocimiento para los cuales existen algoritmos que son similares en complejidad computacional. Dos representantes importantes:

Clase P

La clase P contiene todos aquellos problemas cuya solución se considera "rápida", es decir, cuyo tiempo de solución depende polinomialmente del tamaño de la entrada. Esto incluye ordenar , buscar en una matriz, descubrir la conectividad de los gráficos y muchos otros.

Clase NP

La clase NP contiene problemas que una máquina de Turing no determinista puede resolver en un número polinomial de pasos a partir del tamaño de la entrada. Su solución puede comprobarse mediante una máquina de Turing determinista en un número polinomial de pasos. Cabe señalar que una máquina de Turing no determinista es solo un modelo abstracto, mientras que las computadoras modernas corresponden a una máquina de Turing determinista con memoria limitada. Debido a que una máquina de Turing determinista se puede considerar como un caso especial de una máquina de Turing no determinista , la clase NP incluye la clase P, así como algunos problemas para los cuales solo los algoritmos que dependen exponencialmente del tamaño de entrada (es decir, son ineficientes para grandes entradas) se sabe que resuelven. La clase NP incluye muchos problemas famosos, como el problema del viajante de comercio , el problema de satisfacibilidad para fórmulas booleanas , la factorización , etc.

El problema de la igualdad de las clases P y NP

La cuestión de la igualdad de estas dos clases se considera uno de los problemas abiertos más difíciles en el campo de la informática teórica. El Clay Mathematical Institute ha incluido este problema en su lista de Problemas del Milenio , ofreciendo una recompensa de un millón de dólares por su solución.

Véase también

Notas

↑ 1 2Cormen , Thomas H.; Leizerson, Carlos I.; Rivest, Ronald L.; Stein, Clifford. Algoritmos: construcción y análisis, 2.ª edición = Introducción a los algoritmos, segunda edición. - M. : "Williams" , 2005. - ISBN 5-8459-0857-4 .
↑ AA Zykov. Fundamentos de la teoría de grafos. - 3ra ed. - M. : Vuzovskaya kniga, 2004. - S. 10. - 664 p. — ISBN 5-9502-0057-8 .

Enlaces

Girsh EA " Complejidad Computacional y Fundamentos de Criptografía " . Un curso de conferencias que describen los conceptos básicos de la complejidad computacional y la criptografía.
Yuri Lifshits " Problemas modernos de la informática teórica " . Curso de conferencias sobre algoritmos para problemas NP-difíciles.
A. A. Razborov . Informática teórica: la mirada de un matemático // Computerra . - 2001. - Nº 2 . (enlace descendente)(enlace alternativo)
A. A. RAZBOROV Sobre la complejidad de los cálculos // Educación matemática . - MTSNMO , 1999. - N° 3 . - S. 127-141 .

diccionarios y enciclopedias	gran ruso

Clases de complejidad de algoritmos
Considerado ligero	DLOGTIME CA 0 ACC 0 TC0 [ es L SL RL Países Bajos CAROLINA DEL NORTE SC CC PAGS P-completa ZPP PR BPP BQP EQP APX
Se supone que es difícil	UP notario público NP completo co-NP co-NP-completo AM MA QMA PH ⊕P PÁGINAS #PAGS #P- IP ESPACIO P PSPACE-completo
Considerado difícil	EXPTIME NEXPTIME EXPESPACIO 2-EXPTIM PRIMARIA R PR RE RE-completar Co-RE Co-RE-completo TODOS