13 Notación asintótica Objetivo: simplificar el análisis eliminando la información innecesaria (como "redondeo" 1,000,001~1,000,000) Queremos decir de manera formal 3n2 ~ n2 Notación "O-grande (Big-Oh)": dadas las funciones f(n) and g(n), decimos que f(n) es O(g(n) ) si y solo si hay constantes positivas c y n0 tal que f(n)= c g(n) para n = n0
14 Notación asintótica: ejemplo Para funciones f(n) y g(n) (derecha) hay constantes positivas c y n0 tales que: f(n)=c g(n) for n = n0
conclusión: 2n+6 is O(n).
15 Notación asintótica: ejemplo Otro caso. n2 no es O(n) debido a que no hay c y n0 tal que: n2 = cn para n = n0
(como se ve en el gráfico, no importa cuan grande se escoge c hay un n suficientemente grande que n2>cn ) .
16 Notación asintótica Nota: Aun cuando es correcto decir que "7n – 3 es O(n3)", es mejor decir "7n – 3 es O(n)", esto es, se debe hacer la aproximación lo más cerca posible
Regla simple: Eliminar los términos de bajo orden y las constantes 7n-3 es O(n) 8n2log n + 5n2 + n es O(n2log n)
17 Notación asintótica (terminología) Clases especiales de algoritmos: logaritmico: O(log n) lineal: O(n) cuadratico: O(n2) polinomico: O(nk), k = 1 exponencial: O(an), n > 1
"Alternativos" de Big-Oh ? (f(n)): Big Omega– cota inferior asintótica ? (f(n)): Big Theta– cota promedio asintótica
18 Tiempo de ejecución Usar la notación Big-Oh para expresar el número de operaciones primitivas ejecutadas como función del tamaño de entrada. Ejemplo: decimos que el algoritmo arrayMax se ejecuta en tiempo O(n). Comparación de tiempos de ejecución asintóticos – un algoritmo que corre en tiempo O(n) es mejor que uno que corre en tiempo O(n2) – de forma similar, O(log n) es mejor que O(n) – jerarquía de funciones: log n < < n < < n2 < < n3 < < 2n Cuidado! Con los factores constantes muy grandes. Un algoritmo que corre en tiempo 1,000,000 n todavía es O(n) pero puede ser menor eficiente para un conjunto de datos que uno que corre en tiempo 2n2, que es O(n2)
19 Ejemplo de análisis asintótico Algoritmo para calcular promedios prefijos:
Algorithm prefixAverages1(X): Input: Array X de números de n-elementos. Output: Array A de números de n -elementos tal que A[i] es el promedio de los elementos X[0], … , X[i]. Sea A un array de n números. for i? 0 to n – 1 do a ? 0 for j ? 0 to i do a ? a + X[j] A[i] ? a/(i+ 1) return array A Análisis: O(n2)
20 Ejemplo de análisis asintótico Otro algoritmo para calcular promedios prefijos: A[i-1] = (X[0] + X[1] +…+ X[i-1])/i A[i] = (X[0] + X[1] +…+ X[i-1] + X[i])/(i+1) Algorithm prefixAverages2(X): Input: Array X de números de n-elementos. Output: Array A de números de n -elementos tal que A[i] es el promedio de los elementos X[0], … , X[i]. Sea A un array de n números. s? 0 for i ? 0 to n do s ? s + X[i] A[i] ? s/(i+ 1) return array A Análisis: O(n)
21 Complejidad en la práctica Considerando 109 instrucciones/segundo
22 Análisis de algoritmos recursivos Algorithm recursiveMax(A, n): Input: Un array A que almacena n enteros. Output: El máximo elemento en A. if n = 1 then return A[0] return max {recursiveMax(A, n-1), A[n-1] } Se usan ecuaciones de recurrencia
3 si n = 1 T(n) = T(n-1) + 7 en otro caso
Forma cerrada: T(n) = 7(n-1) + 3
23 Elementos matemáticos Sumatorios y series Logaritmos y exponentes propiedades de logaritmos: logb(xy) = logbx + logby logb (x/y) = logbx – logby logbxa = alogbx logba= logxa/logxb propiedades de exponenciales: a(b+c) = aba c abc = (ab)c ab /ac = a(b-c) b = a logab bc = a c*logab Funciones especiales Floor: ?x? = el mayor entero = x Ceiling: ?x? = el menor entero = x
24 Elementos matemáticos Técnicas de justificación (demostración) Ejemplo y contraejemplo Contrapositivo y Contradicción Inducción Invariantes de bucle Probabilidades (algoritmos que usan random o análisis de rendimiento promedio de un algoritmo)
25 Otras técnicas Amortización Método contable Funciones potenciales Experimentación Configuración Selección de la cuestión Decisión de lo que va a medir (Referencias a memoria, Comparaciones, Operaciones aritméticas) Generación de los datos de prueba Codificación de la solución y realización del experimento Análisis de datos y visualización La prueba del cociente La prueba de potencia
| Página siguiente |