Complejidad temporal
En ambos casos, la complejidad temporal generalmente se expresa como una función del tamaño de la entrada.
Por lo tanto, la complejidad temporal se expresa comúnmente usando la notación O grande, típicamente
Las complejidades algorítmicas se clasifican según el tipo de función que aparece en la notación O grande.
logaritmo iterado Se dice que un algoritmo es tiempo constante (también escrito como tiempo O(1)) si el valor de T(n) está limitado por un valor que no depende del tamaño de la entrada.
Por ejemplo, acceder a cualquier elemento individual en una matriz requiere tiempo constante, ya que solo se debe realizar una operación para localizarlo.
Sin embargo, encontrar el valor mínimo en una matriz desordenada no es una operación de tiempo constante ya que es necesario escanear cada elemento de la matriz para determinar el valor mínimo.
Dado que log a n y log b n están relacionados por un multiplicador constante, y dicho multiplicador es irrelevante para la clasificación big-O, el uso estándar para algoritmos de tiempo logarítmico es O(log n ) independientemente de la base del logaritmo que aparece en la expresión de T. Los algoritmos que toman tiempo logarítmico se encuentran comúnmente en operaciones con árboles binarios o cuando se usa la búsqueda binaria.
Bajo estas hipótesis, la prueba de si una palabra w está en el diccionario se puede hacer en tiempo logarítmico: considere
Este algoritmo es similar al método utilizado a menudo para encontrar una entrada en un diccionario de papel.
En particular, esto incluye algoritmos con las complejidades de tiempo definidas anteriormente.
Por lo general, para una entrada que se representa como una cadena binaria b1,..., bk se supone que el algoritmo puede solicitar y obtener el valor de bi para cualquier i en tiempo O(1).
Los algoritmos de tiempo sub-lineal suelen ser aleatorios y solo proporcionan soluciones aproximadas.
Hay varias tecnologías de hardware que explotan el paralelismo para proporcionar esto.
Se dice que un algoritmo es de tiempo subcuadrático si T (n) = O(n2).
Estos dos conceptos solo son relevantes si las entradas a los algoritmos consisten en enteros.
y, por lo tanto, exponencial en lugar de polinomico en el espacio utilizado para representar la entrada.
El algoritmo euclidiano para calcular el máximo divisor común de dos enteros es un ejemplo.
Al mismo tiempo, el número de operaciones aritméticas no puede estar limitado por el número de enteros en la entrada (que es constante en este caso, siempre hay solo dos enteros en la entrada).
Debido a la última observación, el algoritmo no se ejecuta en un tiempo fuertemente polinómico.
Se dice que un algoritmo toma tiempo superpolinomial si T (n) no está limitado por ningún polinomio.
Dado que el problema P versus NP no está resuelto, actualmente no se sabe de un algoritmo para un problema NP completo que se ejecute en tiempo polinómico.
En ese caso, esta reducción no prueba que el problema B sea NP-hard; esta reducción solo muestra que no existe un algoritmo de tiempo polinómico para B a menos que exista un algoritmo de tiempo cuasi polinómico para 3SAT (y, por lo tanto, todo NP).
Todos los algoritmos más conocidos para problemas NP-completos como 3SAT, etc. toman tiempo exponencial.
Aquí "tiempo sub-exponencial" se entiende como la segunda definición presentada a continuación.
Esta conjetura (para el problema k-SAT) se conoce como la hipótesis del tiempo exponencial.
Generalmente no hay consenso respecto a la definición precisa de "sub-exponencial",[16] enumeramos las dos más utilizados a continuación: Se dice que un problema puede resolverse con un tiempo sub-exponencial si se puede resolver en tiempos de ejecución cuyos logaritmos crecen más lentamente que cualquier polinomio dado.
(En 2015–2017, Babai redujo la complejidad de este problema al tiempo cuasi polinomial.)
La hipótesis del tiempo exponencial (ETH ) es que 3SAT, el problema de satisfacción de las fórmulas booleanas en forma conjuntiva normal con, como máximo, tres literales por cláusula y con n variables, no puede resolverse en el tiempo 2o(n) .
Con m denotando el número de cláusulas, ETH es equivalente a la hipótesis de que k-SAT no puede resolverse en el tiempo 2o(m) para cualquier entero k ≥ 3[24] La hipótesis del tiempo exponencial implica P ≠ NP .
En el caso promedio, cada paso a través del algoritmo bogosort examinará uno de los n!
