¿Cuál es la complejidad del tiempo de un algoritmo?

Uno puede mejorar la velocidad del algoritmo A para correr dos veces más rápido. Esto es bueno, pero también puedes lograrlo con una computadora más rápida. Si el tamaño del problema se vuelve 10 veces mayor, el tiempo de ejecución del algoritmo seguirá aumentando con la misma velocidad.

Una mejora es mucho más notable cuando mejora su notación O grande, lo que significa que aumentar el tamaño del problema no aumenta el tiempo de ejecución con la misma velocidad.

Pero, ¿cómo medir la gran O?

Considere un algoritmo A1 con un bucle:

para i = 1 a N do

…

Aquí, si N aumenta 10 veces, el algoritmo se ejecuta 10 veces más lento, por lo que la complejidad es O (N).

pero en el algoritmo A2 con dos bucles:

para i = 1 a N do

para j = 1 a 2N do

…

Aumento de N con el orden de 10 resultados para el cálculo de 100 veces más lento, por lo que la complejidad es O (N ^ 2).

No nos importa mucho O (2N ^ 2) y O (N ^ 2). Las tasas constantes no importan.

Sin embargo, se cuenta el orden de los logaritmos. Por ejemplo, la ordenación rápida tiene una complejidad promedio de O (N log N).

Los algoritmos de clasificación tienen una tabla de comparación significativa. Sería genial echarles un vistazo.

Puede consultar el siguiente video sobre la complejidad temporal y espacial de los algoritmos. (Big O, Big Omega y Big Theta se publicarán pronto)

Aquí hay una breve descripción de lo que explica el video:

La complejidad del tiempo es esencialmente el tiempo de ejecución del algoritmo representado como una función de la entrada proporcionada, suponiendo que todos los demás parámetros que afectan este tiempo sean constantes.

La complejidad de tiempo para cualquier algoritmo se puede calcular utilizando los siguientes Supuestos de Complejidad de Tiempo:

• Las operaciones de forma +, -, * /, y, o, &, |, ^, ==, <,>, <=,> =, = se denominan operaciones elementales y se supone que toman una cantidad de tiempo constante .
• Complejidad de tiempo = kc; donde c es una constante dependiente de la plataforma en la que se ejecuta el algoritmo, k es el número de operaciones elementales que ocurren en función de las variables de entrada al algoritmo.

En el video se han cubierto ejemplos de hacer lo mismo para algún programa.

PD. Suscríbase si le gusta el contenido del video.

Básicamente es una métrica abstracta que caracteriza la tasa de crecimiento de su problema. Nos da una idea de qué tan rápido aumentará el tiempo de ejecución del algoritmo a medida que aumenta el tamaño del problema (tamaño de entrada). La complejidad (u orden) de una función generalmente se expresa en notación BigO: notación Big O – Wikipedia.