¿Cuál es el significado de ‘orden de crecimiento’ en el análisis de algoritmos y cómo podemos encontrar el orden de crecimiento de un algoritmo dado?

El orden de crecimiento de un algoritmo es una forma de decir / predecir cómo cambia el tiempo de ejecución de un programa y el espacio / memoria que ocupa con el tamaño de entrada.

La forma más famosa es la notación Big-Oh. Da la peor posibilidad para un algoritmo.

Por ejemplo, un programa toma O (n) tiempo significa que toma como máximo n operaciones para calcular la respuesta. Ahora, si su entrada para n es 10 ^ 6, toma 10 ^ 6 operaciones, mientras que un algoritmo O (n ^ 2) toma 10 ^ 12 operaciones para la misma entrada.

Para encontrar el orden de crecimiento de un programa: en general, se supone que la parte del programa que requiere la mayor cantidad de tiempo es el orden de crecimiento en el caso de la notación Big-Oh.

Tome un bucle for: for (i = 0; i

ahora si tienes un bucle anidado como:

para (i = 0; i

{

para (j = 0; j

…

}

entonces esto tomará n operaciones para cada valor de i debido al bucle j y tengo n valores posibles. Por lo tanto, es O (n ^ 2).

Si le resulta difícil de entender, le sugiero que tome un curso de algoritmos en línea para salirse de los bloques.

El orden de crecimiento significa cómo aumentará o disminuirá el tiempo y el espacio de su algoritmo cuando aumente o disminuya el tamaño de la entrada.

Uno no puede medir exactamente cuál es el orden de crecimiento de cualquier algoritmo wrt input size “n”; así que aproximamos el orden de crecimiento de nuestro algoritmo o hormiga usando notaciones Big-Oh.

Big-Oh es el más famoso porque proporciona el límite superior del algoritmo, es decir,

si obtenemos O (f (x)) = g (x), entonces estamos seguros de que el crecimiento de la función f (x) nunca puede superar la función g (x).

¡Espero eso ayude!