Complejidad computacional

En informática, la complejidad computacional o simplemente complejidad de un algoritmo es la cantidad de recursos necesarios para ejecutarlo. Se presta especial atención al tiempo de cálculo (generalmente medido por el número de operaciones elementales necesarias) y los requisitos de almacenamiento de memoria. La complejidad de un problema es la complejidad de los mejores algoritmos que permiten resolver el problema.

El estudio de la complejidad de algoritmos dados explícitamente se denomina análisis de algoritmos, mientras que el estudio de la complejidad de problemas se denomina teoría de la complejidad computacional. Ambas áreas están muy relacionadas, ya que la complejidad de un algoritmo es siempre un límite superior en la complejidad del problema resuelto por este algoritmo. Además, para diseñar algoritmos eficientes, a menudo es fundamental comparar la complejidad de un algoritmo específico con la complejidad del problema a resolver. Además, en la mayoría de los casos, lo único que se sabe sobre la complejidad de un problema es que es menor que la complejidad de los algoritmos conocidos más eficientes. Por lo tanto, existe una gran superposición entre el análisis de algoritmos y la teoría de la complejidad.

Como la cantidad de recursos necesarios para ejecutar un algoritmo generalmente varía con el tamaño de la entrada, la complejidad generalmente se expresa como una función n → f(n), donde n es el tamaño de la entrada y f(n) es la complejidad del peor de los casos (el máximo de la cantidad de recursos que se necesitan sobre todas las entradas de tamaño n) o la complejidad del caso promedio (el promedio de la cantidad de recursos sobre todas las entradas de tamaño n). La complejidad del tiempo generalmente se expresa como el número de operaciones elementales requeridas en una entrada de tamaño n, donde se supone que las operaciones elementales toman una cantidad de tiempo constante en una computadora dada y cambia solo por un factor constante cuando se ejecuta en una computadora diferente. La complejidad del espacio generalmente se expresa como la cantidad de memoria requerida por un algoritmo en una entrada de tamaño n.

Recursos

Tiempo

El recurso más comúnmente considerado es el tiempo. Cuando la "complejidad" se usa sin calificación, esto generalmente significa complejidad de tiempo.

Las unidades habituales de tiempo (segundos, minutos, etc.) no se utilizan en la teoría de la complejidad porque dependen demasiado de la elección de un ordenador específico y de la evolución de la tecnología. Por ejemplo, una computadora de hoy puede ejecutar un algoritmo significativamente más rápido que una computadora de la década de 1960; sin embargo, esta no es una característica intrínseca del algoritmo, sino más bien una consecuencia de los avances tecnológicos en el hardware de las computadoras. La teoría de la complejidad busca cuantificar los requisitos de tiempo intrínsecos de los algoritmos, es decir, las restricciones de tiempo básicas que un algoritmo colocaría en cualquier computadora. Esto se logra contando el número de operaciones elementales que se ejecutan durante el cómputo. Se supone que estas operaciones toman un tiempo constante (es decir, no se ven afectadas por el tamaño de la entrada) en una máquina determinada y, a menudo, se denominan pasos.

Complejidad de bits

Formalmente, la complejidad de bits se refiere al número de operaciones en bits que se necesitan para ejecutar un algoritmo. Con la mayoría de los modelos de computación, iguala la complejidad del tiempo hasta un factor constante. En las computadoras, la cantidad de operaciones en palabras de máquina que se necesitan también es proporcional a la complejidad de bits. Entonces, la complejidad de tiempo y la complejidad de bits son equivalentes para modelos realistas de computación.

Espacio

Otro recurso importante es el tamaño de la memoria de la computadora que se necesita para ejecutar algoritmos.

Comunicación

Para la clase de algoritmos distribuidos que comúnmente son ejecutados por múltiples partes que interactúan, el recurso de mayor interés es la complejidad de la comunicación. Es la cantidad necesaria de comunicación entre las partes ejecutoras.

Otros

El número de operaciones aritméticas es otro recurso que se utiliza habitualmente. En este caso, se habla de complejidad aritmética. Si se conoce un límite superior en el tamaño de la representación binaria de los números que ocurren durante un cálculo, la complejidad del tiempo es generalmente el producto de la complejidad aritmética por un factor constante.

Para muchos algoritmos el tamaño de los enteros que se utilizan durante una computación no está atado, y no es realista considerar que las operaciones aritméticas toman un tiempo constante. Por lo tanto, la complejidad del tiempo, generalmente llamada poco complejidad en este contexto, puede ser mucho mayor que la complejidad aritmética. Por ejemplo, la complejidad aritmética de la computación del determinante de un n×n matriz de enteros O()n3){displaystyle O(n^{3}} para los algoritmos habituales (Erradicación gausiana). La complejidad del bit de los mismos algoritmos es exponencial en n, porque el tamaño de los coeficientes puede crecer exponencialmente durante el cálculo. Por otro lado, si estos algoritmos se unen con aritmética multimodular, la complejidad del bit puede reducirse a O~(n4).

Al ordenar y buscar, el recurso que generalmente se considera es el número de comparaciones de entradas. Esta es generalmente una buena medida de la complejidad del tiempo si los datos se organizan adecuadamente.

Complejidad en función del tamaño de entrada

Es imposible contar el número de pasos de un algoritmo en todas las entradas posibles. Como la complejidad generalmente aumenta con el tamaño de la entrada, la complejidad generalmente se expresa como una función del tamaño n (en bits) de la entrada, y por lo tanto, la complejidad es una función de n. Sin embargo, la complejidad de un algoritmo puede variar drásticamente para diferentes entradas del mismo tamaño. Por lo tanto, se utilizan comúnmente varias funciones de complejidad.

La complejidad del peor caso es el máximo de la complejidad sobre todas las entradas de tamaño n, y la complejidad del caso promedio es el promedio de la complejidad sobre todas las entradas de tamaño n (esto tiene sentido, ya que el número de entradas posibles de un tamaño dado es finito). Generalmente, cuando la "complejidad" se utiliza sin especificarse más, esta es la complejidad de tiempo en el peor de los casos que se considera.

Complejidad asintótica

Por lo general, es difícil calcular con precisión el peor de los casos y la complejidad del caso promedio. Además, estos valores exactos proporcionan poca aplicación práctica, ya que cualquier cambio de computadora o de modelo de cálculo cambiaría un poco la complejidad. Además, el uso de recursos no es crítico para valores pequeños de n, y esto hace que, para valores pequeños n, la facilidad de implementación es generalmente más interesante que una baja complejidad.

Por estas razones, uno generalmente se enfoca en el comportamiento de la complejidad para grandes n, es decir, en su comportamiento asintótico cuando n tiende al infinito. Por lo tanto, la complejidad generalmente se expresa utilizando la notación O grande.

Por ejemplo, el algoritmo habitual para la multiplicación del entero tiene una complejidad O()n2),{displaystyle O(n^{2}),} esto significa que hay una constante cu{displaystyle c_{u} tal que la multiplicación de dos enteros de la mayoría n dígitos se pueden hacer en un tiempo menos que cun2.{displaystyle c_{u}n^{2} Este límite es agudo en el sentido de que la peor complejidad y la complejidad media son Ω Ω ()n2),{displaystyle Omega (n^{2}),} que significa que hay una constante cl{displaystyle c_{l} tales que estas complejidades son más grandes que cln2.{displaystyle c_{l}n^{2} El radio no aparece en esta complejidad, ya que el cambio de radio cambia solamente las constantes cu{displaystyle c_{u} y cl.{displaystyle c_{l}

Modelos de computación

La evaluación de la complejidad se basa en la elección de un modelo de cálculo, que consiste en definir las operaciones básicas que se realizan en una unidad de tiempo. Cuando el modelo de computación no se especifica explícitamente, generalmente se entiende como una máquina de Turing multicinta.

Modelos deterministas

Un modelo determinista de computación es un modelo de computación tal que los estados sucesivos de la máquina y las operaciones a realizar están completamente determinadas por el estado precedente. Históricamente, los primeros modelos deterministas fueron las funciones recursivas, el cálculo lambda y las máquinas de Turing. El modelo de máquinas de acceso aleatorio (también llamadas máquinas RAM) también se usa ampliamente, como una contraparte más cercana a las computadoras reales.

Cuando no se especifica el modelo de computación, generalmente se asume que es una máquina de Turing multicinta. Para la mayoría de los algoritmos, la complejidad del tiempo es la misma en las máquinas de Turing multicinta que en las máquinas RAM, aunque puede ser necesario tener cuidado en cómo se almacenan los datos en la memoria para obtener esta equivalencia.

Cálculo no determinista

En un modelo de cálculo no determinista, como las máquinas de Turing no deterministas, se pueden realizar algunas elecciones en algunos pasos del cálculo. En la teoría de la complejidad, uno considera todas las elecciones posibles simultáneamente, y la complejidad del tiempo no determinista es el tiempo necesario, cuando siempre se toman las mejores decisiones. En otras palabras, se considera que el cómputo se realiza simultáneamente en tantos procesadores (idénticos) como se necesiten, y el tiempo de cómputo no determinista es el tiempo empleado por el primer procesador que finaliza el cómputo. Este paralelismo es parcialmente compatible con la computación cuántica a través de estados entrelazados superpuestos al ejecutar algoritmos cuánticos específicos, como p. Factorización de Shor de números enteros pequeños (a partir de marzo de 2018: 21 = 3 × 7).

Incluso cuando dicho modelo de cálculo aún no es realista, tiene importancia teórica, principalmente relacionada con el problema P = NP, que cuestiona la identidad de las clases de complejidad formadas al tomar "tiempo polinomial" y "tiempo polinómico no determinista" como mínimo límites superiores. La simulación de un algoritmo NP en una computadora determinista generalmente lleva un "tiempo exponencial". Un problema está en la clase de complejidad NP, si se puede resolver en tiempo polinomial en una máquina no determinista. Un problema es NP-completo si, en términos generales, está en NP y no es más fácil que cualquier otro problema NP. Muchos problemas combinatorios, como el problema de la mochila, el problema del viajante de comercio y el problema de la satisfacibilidad booleana son NP-completos. Para todos estos problemas, el algoritmo más conocido tiene una complejidad exponencial. Si cualquiera de estos problemas pudiera resolverse en tiempo polinomial en una máquina determinista, entonces todos los problemas NP también podrían resolverse en tiempo polinomial, y uno tendría P = NP. A partir de 2017, generalmente se conjetura que P ≠ NP, con la implicación práctica de que los peores casos de problemas NP son intrínsecamente difíciles de resolver, es decir, toman más tiempo que cualquier período de tiempo razonable (¡décadas!) para longitudes interesantes de entrada.

Cómputo paralelo y distribuido

La computación paralela y distribuida consiste en dividir la computación en varios procesadores, que funcionan simultáneamente. La diferencia entre los diferentes modelos radica principalmente en la forma de transmitir la información entre procesadores. Normalmente, en la computación paralela la transmisión de datos entre procesadores es muy rápida, mientras que en la computación distribuida la transmisión de datos se realiza a través de una red y, por lo tanto, es mucho más lenta.

El tiempo necesario para un cálculo en procesadores N es al menos el cociente por N del tiempo que necesita un solo procesador. De hecho, este límite teóricamente óptimo nunca se puede alcanzar, porque algunas subtareas no se pueden paralelizar y algunos procesadores pueden tener que esperar un resultado de otro procesador.

El principal problema de complejidad es, por lo tanto, diseñar algoritmos tales que el producto del tiempo de cálculo por el número de procesadores sea lo más cercano posible al tiempo necesario para el mismo cálculo en un solo procesador.

Computación cuántica

Una computadora cuántica es una computadora cuyo modelo de computación se basa en la mecánica cuántica. La tesis de Church-Turing se aplica a las computadoras cuánticas; es decir, cada problema que puede resolver una computadora cuántica también puede resolverse con una máquina de Turing. Sin embargo, en teoría, algunos problemas pueden resolverse con una complejidad de tiempo mucho menor utilizando una computadora cuántica en lugar de una computadora clásica. Esto es, por el momento, puramente teórico, ya que nadie sabe cómo construir una computadora cuántica eficiente.

La teoría de la complejidad cuántica se ha desarrollado para estudiar las clases de complejidad de los problemas resueltos mediante computadoras cuánticas. Se utiliza en la criptografía poscuántica, que consiste en diseñar protocolos criptográficos resistentes a los ataques de los ordenadores cuánticos.

Complejidad del problema (límites inferiores)

La complejidad de un problema es el mínimo de las complejidades de los algoritmos que pueden resolver el problema, incluidos los algoritmos desconocidos. Así, la complejidad de un problema no es mayor que la complejidad de cualquier algoritmo que resuelva los problemas.

Se sigue que cada complejidad que se expresa con notación O grande es una complejidad del algoritmo así como del problema correspondiente.

Por otro lado, generalmente es difícil obtener límites inferiores no triviales para la complejidad del problema y existen pocos métodos para obtener tales límites inferiores.

Para resolver la mayoría de los problemas, es necesario leer todos los datos de entrada, que normalmente necesita un tiempo proporcional al tamaño de los datos. Por lo tanto, estos problemas tienen una complejidad que es al menos lineal, es decir, usando una gran notación de omega, una complejidad Ω Ω ()n).{displaystyle Omega (n). }

La solución de algunos problemas, típicamente en álgebra computacional y geometría algebraica computacional, puede ser muy grande. En tal caso, la complejidad se ve limitada por el tamaño máximo de la salida, ya que la salida debe ser escrita. Por ejemplo, un sistema de ecuaciones polinómicas de grado d en n indeterminados puede tener hasta dn{displaystyle d^{n} soluciones complejas, si el número de soluciones es finito (este es el teorema de Bézout). Como estas soluciones deben ser escritas, la complejidad de este problema es Ω Ω ()dn).{displaystyle Omega (d^{n}). } Para este problema, un algoritmo de complejidad dO()n){displaystyle d^{O(n)} es conocido, que puede ser considerado como asintotically cuasi-optimal.

Un límite inferior no lineal Ω Ω ()nlog⁡ ⁡ n){displaystyle Omega (nlog n)} es conocido por el número de comparaciones necesarias para un algoritmo de clasificación. Así, los algoritmos de clasificación mejores son óptimos, ya que su complejidad es O()nlog⁡ ⁡ n).{displaystyle O(nlog n).} Este límite inferior resulta del hecho de que hay n! maneras de ordenar n objetos. Como cada comparación se divide en dos partes este conjunto de n! órdenes, el número de órdenes N de las comparaciones necesarias para distinguir todas las órdenes deben verificar n!,}" xmlns="http://www.w3.org/1998/Math/MathML">2N■n!,{displaystyle 2^{N}¡No!n!,}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/67b9c361fc15c8a355bf19a7e93d3feb9b794fa2" style="vertical-align: -0.671ex; width:8.641ex; height:3.009ex;"/> que implica N=Ω Ω ()nlog⁡ ⁡ n),{displaystyle N=Omega (nlog n),} por la fórmula de Stirling.

Un método estándar para conseguir límites inferiores de complejidad consiste en Reducción un problema para otro problema. Más precisamente, supongamos que uno puede codificar un problema A de tamaño n en un subproblema de tamaño f()n) de un problema B, y que la complejidad de A es Ω Ω ()g()n)).{displaystyle Omega (g(n)). } Sin pérdida de generalidad, se puede suponer que la función f aumentos con n y tiene una función inversa h. Entonces la complejidad del problema B es Ω Ω ()g()h()n))).{displaystyle Omega (g(h(n))). } Este es el método que se utiliza para demostrar que, si P ل NP (una conjetura sin resolver), la complejidad de cada problema completo de NP es Ω Ω ()nk),{displaystyle Omega (n^{k}),} para cada entero positivo k.

Uso en el diseño de algoritmos

La evaluación de la complejidad de un algoritmo es una parte importante del diseño del algoritmo, ya que brinda información útil sobre el rendimiento que se puede esperar.

Es una idea errónea común que la evaluación de la complejidad de los algoritmos se volverá menos importante como resultado de la ley de Moore, que plantea el crecimiento exponencial del poder de las computadoras modernas. Esto es incorrecto porque este aumento de potencia permite trabajar con datos de entrada grandes (gran datos). Por ejemplo, cuando uno quiere ordenar alfabéticamente una lista de algunos cientos de entradas, como la bibliografía de un libro, cualquier algoritmo debe funcionar bien en menos de un segundo. Por otro lado, para una lista de un millón de entradas (los números telefónicos de una ciudad grande, por ejemplo), los algoritmos elementales que requieren O()n2){displaystyle O(n^{2}} las comparaciones tendrían que hacer un billón de comparaciones, que necesitarían alrededor de tres horas a la velocidad de 10 millones de comparaciones por segundo. Por otro lado, el rápido surtido y la fusión requieren sólo nlog2⁡ ⁡ n{displaystyle nlog _{2}n} comparaciones (como la complejidad media de la primera, como la peor complejidad de la segunda). Para n 1,000,000, esto da aproximadamente 30.000 comparaciones, que sólo tomaría 3 segundos a 10 millones de comparaciones por segundo.

Así, la evaluación de la complejidad puede permitir eliminar muchos algoritmos ineficientes antes de cualquier implementación. Esto también se puede usar para ajustar algoritmos complejos sin probar todas las variantes. Al determinar los pasos más costosos de un algoritmo complejo, el estudio de la complejidad permite centrar también en estos pasos el esfuerzo por mejorar la eficiencia de una implementación.