Nada

Notación O grande

Ing. Bruno López Takeyas

NOTACIÓN O GRANDE
• El análisis de algoritmos estima el consumo de recursos de un algoritmo. • Esto nos permite comparar los costos relativos de dos o más algoritmos para resolver el mismo problema. • El análisis de algoritmos también les da una herramienta a los diseñadores de algoritmos para estimar si una solución propuesta es probable quesatisfaga las restricciones de recursos de un problema. • El concepto de razón de crecimiento, es la razón a la cual el costo de un algoritmo crece conforme el tamaño de la entrada crece.

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Notación O grande

Ing. Bruno López Takeyas

Introducción
• ¿Cómo comparar dos algoritmos para resolver un mismo problema entérminos de eficiencia? • El análisis de algoritmos mide la eficiencia de un algoritmo, conforme crece el tamaño de la entrada. • Usualmente se mide el tiempo de ejecución de un algoritmo, y el almacenamiento primario y secundario que consume. • De consideración principal para estimar el desempeño de un algoritmo, es el operaciones básicas número de requeridas por el algoritmo para procesar unaentrada de cierto tamaño.

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Notación O grande

Ing. Bruno López Takeyas

• Ejemplo: Algoritmo de búsqueda secuencial del máximo. T(n) = cn (donde c es el tiempo que lleva examinar una variable).
int maximo (int* arreglo, int n) { int mayor=0; for(int i = 0; i < n; i++) if(arreglo[i] > mayor) mayor = arreglo[i];return mayor; }

• Ejemplo: el tiempo requerido para copiar la primera posición de un arreglo es siempre c1 (independientemente de n). Así T(n) = c1. • Otro ejemplo :
Sum=0 ; for(i=0 ; i < n ; i++) for(j=0; j < n; j++) sum++;
http://www.itnuevolaredo.edu.mx/takeyas Email: takeyas@itnuevolaredo.edu.mx

Notación O grande

Ing. Bruno López Takeyas

¿Cuál es el tiempo de ejecución de estefragmento de código? T(n) = c2 n2 (c2 es el tiempo en incrementar una variable). • El concepto de razón de crecimiento es extremadamente importante. Nos permite comparar el tiempo de ejecución de dos algoritmos sin realmente escribir dos programas y ejecutarlas en la misma máquina. • Una razón de crecimiento de cn se le llama a menudo razón de crecimiento lineal. • Si la razón de crecimiento tieneel factor n2, se dice que tiene una razón de crecimiento cuadrático.

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Notación O grande

Ing. Bruno López Takeyas

• Si el tiempo es del orden 2n se dice que tiene una razón de crecimiento exponencial. notemos que 2n> 2n2 > log n también para toda a, b > 1, na > (log n)b y na > log nb para toda a, b >1, an >nb

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Notación O grande

Ing. Bruno López Takeyas

Mejor, peor y caso promedio
• Para algunos algoritmos, diferentes entradas (inputs) para un tamaño dado pueden requerir diferentes cantidades de tiempo. • Por ejemplo, consideremos el problema de encontrar la posición particular de un valor K, dentro de unarreglo de n elementos. (suponiendo que sólo ocurre una vez). Comentar sobre el mejor, peor y caso promedio. • ¿Cuál es la ventaja de analizar cada caso? Si examinamos el peor de los casos, sabemos que al menos el algoritmo se desempeñara de esa forma. • En cambio, cuando un algoritmo se ejecuta muchas veces en muchos tipos de entrada, estamos interesados en el
http://www.itnuevolaredo.edu.mx/takeyasEmail: takeyas@itnuevolaredo.edu.mx

Notación O grande

Ing. Bruno López Takeyas

comportamiento promedio o típico. Desafortunadamente, esto supone que sabemos cómo están distribuidos los datos. • Si conocemos la distribución de los datos, podemos sacar provecho de esto, para un mejor análisis y diseño del algoritmo. Por otra parte, si no conocemos la distribución, entonces lo mejor es...