Análisis asintótico

Algoritmos Computacionales 

Suponiendo que las siguientes funciones indican la complejidad asintótica de algunos algoritmos para resolver un problema, se tienen que ordenar en orden del peor algoritmo al mejor, donde el mejor sería aquél que tarde menos en resolver el problema.

En la imagen se muestran las ocho funciones a ordenar:

Tenemos que:

I. La función que implica mayor comlejidad es f2, porque al elevar una variable a una potencia igual a sí misma, incrementará rápidamente.

II. Parecido al caso anterior pero con la diferencia de que en la base tenemos una constante, tenemos que f1 es la que sigue a esta lista.

III. Ahora tenemos una base a la n elevada a la siete, esto nos daría en una gráfica que se encuentra más abajo de las dos anteriores esta es f3.

IV. Ahora tenemos una logarítmica un tanto engañosa f4, que sabemos de antemano que es mayor a f6 por el hecho de tener una n multiplicando al logaritmo.

V. Si aplicamos propiedades de los logaritmos y simplificamos, tenemos que f7 es la siguiente en nuestra escala.

VI. Una variable multiplicada a una constante grande f8, es menor a la constante elevada al logaritmo.

VII. Ya casi por terminar tenemos f5, porque una raíz es de los mejores casos que se puede tener.

VIII. Por regla vimos que f6, una función logarítmica es mejor a una polinomial.

Este orden lo obtuvimos en colaboración con todos los alumnos de la clase.