¿Por qué análisis de rendimiento?
Hay muchas cosas importantes que deben cuidarse, como la facilidad de uso, la modularidad, la seguridad, la mantenibilidad, etc. ¿Por qué preocuparse por el rendimiento?
La respuesta a esto es simple, podemos tener todas las cosas anteriores solo si tenemos rendimiento. Entonces, el rendimiento es como una moneda a través de la cual podemos comprar todas las cosas anteriores. Otra razón para estudiar el rendimiento es: ¡la velocidad es divertida!
Para resumir, rendimiento == escala. Imagine un editor de texto que pueda cargar 1000 páginas, pero que pueda revisar la ortografía 1 página por minuto O un editor de imágenes que tarde 1 hora en rotar su imagen 90 grados a la izquierda O… lo tiene. Si una función de software no puede hacer frente a la escala de tareas que los usuarios deben realizar, está prácticamente muerta.
Dados dos algoritmos para una tarea, ¿cómo averiguamos cuál es mejor?
Una forma ingenua de hacer esto es implementar ambos algoritmos y ejecutar los dos programas en su computadora para diferentes entradas y ver cuál toma menos tiempo. Hay muchos problemas con este enfoque para el análisis de algoritmos.
1) Es posible que para algunas entradas, el primer algoritmo funcione mejor que el segundo. Y para algunas entradas, el segundo funciona mejor.
2) También podría ser posible que para algunas entradas, el primer algoritmo funcione mejor en una máquina y el segundo funcione mejor en otra máquina para algunas otras entradas.
El análisis asintótico es la gran idea que maneja los problemas anteriores en el análisis de algoritmos. En el análisis asintótico, evaluamos el rendimiento de un algoritmo en términos del tamaño de entrada (no medimos el tiempo de ejecución real). Calculamos cómo el tiempo (o espacio) tomado por un algoritmo aumenta con el tamaño de entrada.
Por ejemplo, consideremos el problema de búsqueda (buscar un elemento dado) en una array ordenada. Una forma de buscar es la búsqueda lineal (el orden de crecimiento es lineal) y la otra forma es la búsqueda binaria (el orden de crecimiento es logarítmico). Para comprender cómo el análisis asintótico resuelve los problemas mencionados anteriormente al analizar algoritmos, digamos que ejecutamos la búsqueda lineal en una computadora rápida A y la búsqueda binaria en una computadora lenta By elegimos los valores constantes para las dos computadoras para que nos diga exactamente cuánto tiempo le toma a la máquina dada realizar la búsqueda en segundos. Digamos que la constante de A es 0,2 y la constante de B es 1000, lo que significa que A es 5000 veces más potente que B. Para valores pequeños del tamaño de array de entrada n, la computadora rápida puede tardar menos. Pero, después de un cierto valor del tamaño de la array de entrada, la búsqueda binaria definitivamente comenzará a tomar menos tiempo en comparación con la búsqueda lineal, aunque la búsqueda binaria se ejecute en una máquina lenta. El motivo es que el orden de crecimiento de la búsqueda binaria con respecto al tamaño de entrada es logarítmico, mientras que el orden de crecimiento de la búsqueda lineal es lineal. Por lo tanto, las constantes dependientes de la máquina siempre se pueden ignorar después de un cierto valor de tamaño de entrada.
Estos son algunos tiempos de ejecución para este ejemplo:
Tiempo de ejecución de búsqueda lineal en segundos en A : 0.2 * n
Tiempo de ejecución de búsqueda binaria en segundos en B : 1000*log(n)
------------------------------------------------ |n | Running time on A | Running time on B | ------------------------------------------------- |10 | 2 sec | ~ 1 h | ------------------------------------------------- |100 | 20 sec | ~ 1.8 h | ------------------------------------------------- |10^6 | ~ 55.5 h | ~ 5.5 h | ------------------------------------------------- |10^9 | ~ 6.3 years | ~ 8.3 h | -------------------------------------------------
¿El análisis asintótico siempre funciona?
El análisis asintótico no es perfecto, pero esa es la mejor forma disponible para analizar algoritmos. Por ejemplo, digamos que hay dos algoritmos de clasificación que toman 1000nLogn y 2nLogn de tiempo respectivamente en una máquina. Ambos algoritmos son asintóticamente iguales (el orden de crecimiento es nLogn). Entonces, con el análisis asintótico, no podemos juzgar cuál es mejor ya que ignoramos las constantes en el análisis asintótico.
Además, en el análisis asintótico, siempre hablamos de tamaños de entrada mayores que un valor constante. Es posible que esas entradas grandes nunca se le den a su software y un algoritmo que es asintóticamente más lento, siempre funciona mejor para su situación particular. Por lo tanto, puede terminar eligiendo un algoritmo que sea asintóticamente más lento pero más rápido para su software.
Siguiente – Análisis de Algoritmos | Conjunto 2 (peor, promedio y mejores casos)
Para más detalles, consulte:
Diseño y Análisis de Algoritmos .
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA