Tratar la complejidad algoritmo

Video: Orden de la complejidad de algoritmos

Usted ya sabe que los algoritmos son complejos. Sin embargo, lo que necesita saber la complejidad de un algoritmo es porque cuanto más compleja es, cuanto más tiempo se tarda en ejecutar. La siguiente tabla le ayuda a comprender los diversos niveles de complejidad que se presentan en orden cronológico (del más rápido al más lento) que se ejecuta.

Complejidad	Descripción
complejidad O Constant (1)	Proporciona un tiempo de ejecución invariable, no importa la cantidad de entrada que proporciona. Cada entrada requiere una sola unidad de tiempo de ejecución.
Logarítmica complejidad O (log n)	El número de operaciones crece a un ritmo más lento que el de entrada, por lo que el algoritmo menos eficiente con entradas pequeñas y más eficiente con los más grandes. Un algoritmo típico de esta clase es la búsqueda binaria.
complejidad O lineal (n)	Operaciones crecen con la entrada en una relación 1: 1. Un algoritmo típico es iteración, cuando se escanea entrada una vez y aplicar una operación para cada elemento de la misma.
Linearithmic complejidad O (n log n)	La complejidad es una mezcla entre la complejidad logarítmica y lineal. Es típico de algunos algoritmos inteligentes que se utilizan para ordenar los datos, tales como Mergesortsort, heapsort y ordenación rápida.
Quadratic complejidad O (n²)	Operaciones crecen como un cuadrado del número de entradas. Cuando usted tiene una iteración dentro de otra iteración (llamado iteraciones anidadas en la informática), tiene complejidad cuadrática. Por ejemplo, usted tiene una lista de nombres y, con el fin de encontrar las más similares, se compara cada nombre contra todos los otros nombres. Algunos algoritmos de ordenación menos eficientes presentan tal complejidad: ordenamiento de burbuja, ordenación por selección y ordenación por inserción. Este nivel de complejidad significa que sus algoritmos pueden funcionar durante horas o incluso días antes de llegar a una solución.
Cubic complejidad O (n³)	Operaciones aumentará más rápidamente que la complejidad cuadrática porque ahora tiene varias iteraciones anidadas. Cuando un algoritmo tiene esta orden de complejidad y que necesita para procesar una modesta cantidad de datos (100.000 elementos), el algoritmo puede funcionar durante años. Cuando se tiene una serie de operaciones que es una potencia de la entrada, es común referirse al algoritmo que se ejecuta en tiempo polinómico.
Exponencial complejidad O (2^norte)	El algoritmo toma el doble del número de operaciones anteriores para cada nuevo elemento añadido. Cuando un algoritmo tiene esta complejidad, incluso los pequeños problemas pueden tener para siempre. Muchos algoritmos que realizan búsquedas exhaustivas tienen complejidad exponencial. Sin embargo, el ejemplo clásico de este nivel de complejidad es el cálculo de los números de Fibonacci.
complejidad factorial O (n!)	Este algoritmo presenta una verdadera pesadilla de complejidad debido a la gran cantidad de combinaciones posibles entre los elementos. Imagínese: si la entrada es de 100 objetos, y una operación en el equipo toma 10^-6 segundos (una velocidad razonable para cada equipo hoy en día), necesitará aproximadamente 10¹⁴⁰ años para completar la tarea con éxito (una cantidad imposible de tiempo debido a que la edad del universo se estima como 10₁₄ años). Un famoso problema de la complejidad factorial es el problema del viajante, en la que un vendedor tiene que encontrar la ruta más corta para visitar muchas ciudades y volver a la ciudad de partida.