Regla 3: Ciclos Ejemplo: Un ciclo cuya instrucción: Tiene un O(log n) Se repite n/2 veces Tendrá como orden total… O(½ n log n) = O(n log n). O(g(n)) ˜ O( m * g(n) ) Se repite m veces
Consideraciones especiales En decisiones y ciclos anidados: Analizar el código desde la instrucción más interna hacia el más externa. Tip para los ciclos: ¿“Normalmente” cuál es el orden de la instrucción interna? Si la variable de control se incrementa o decrementa con un valor constante: Orden LINEAL. Si la variable de control se multiplica o divide por un valor constante: Orden LOGARÍTIMICO.
Ejemplo: Sort por intercambio
for (int i=1; i<=n;j++) if (a[ j ] < a[ i ]) intercambia(a[ i ], a[ j ]); ? O( ) 1 1 ? O( ) Regla 2: Decisiones = mayor de las 2 ramas
Ejemplo: Sort por intercambio
for (int i=1; i<=n;j++) if (a[ j ] < a[ i ]) intercambia(a[ i ], a[ j ]);
? O( ) 1 ? O( ) Peor caso: se repite n-1 veces n Regla 3: Ciclos = # veces * orden de la instrucción interna
Ejemplo: Sort por intercambio
for (int i=1; i<=n;j++) if (a[ j ] < a[ i ]) intercambia(a[ i ], a[ j ]);
? O( ) n2 ? O( ) Se repite n-1 veces n Regla 3: Ciclos = # veces * orden de la instrucción interna
Ejemplo: Multiplicación de matrices a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn b11 b12 … b1m b21 b22 … b2m … … … … bn1 bn2 … bnm X c11 = a11*b11+a12 *b21 +…+ a1n *bn1 c12 = a11*b12+a12 *b22 +…+ a1n *bn2 … c21 = a21*b11+a22 *b21 +…+ a2n *bn1 … cmm = am1*b1m+am2 *b2m +…+ amn *bnm c11 c12 … c1m c21 c22 … c2m … … … … cm1 cm2 … cmm = cij = ? aikbkj n k=1
Ejemplo: Multiplicación de matrices
for i = 1 to n do for j = 1 to n do C[i,j] = 0; for k = 1 to n do C[i,j] = C[i,j] + A[i,k]*B[k,j]; O( 1 ) ? O( n ) ? O( n2 ) ? O( n3 ) ? O( 1 ) ?
Regla 4: Recursividad La complejidad de tiempo se obtiene contando la cantidad de veces que se hace la llamada recursiva. Casos que “normalmente” se dan: Orden LINEAL si sólo se tiene una llamada recursiva, con incrementos o decrementos en el parámetro de control. Orden LOGARITMICO si sólo se tiene una llamada recursiva, con multiplicaciones o divisiones en el parámetro de control. Si hay más de una llamada recursiva, el orden puede tender a ser EXPONENCIAL.
Ejemplo: Fibonacci (Iterativo) ant = 1; –> 1 act = 1; –> 1 while (n>2){ –> n-2 + 1 aux = ant + act; –> n-2 ant = act; –> n-2 act = aux; –> n-2 n = n – 1; –> n-2 } –> n-2+1 write (act); –> 1 T(n) = 6n-7
Por lo tanto el orden del algoritmo es O(n)
Ejemplo: Fibonacci (recursivo) Function fibonacci (n:int): int; if (n < 3) return 1; else return fibonacci(n-1) + fibonacci(n-2); ¿Cómo obtener la complejidad de tiempo del algoritmo? Cantidad de llamadas recursivas: 2 en cada llamada. Algoritmo de orden: O(2n/2)
Análisis de Fibonacci (recursivo) ¿Cuántos términos se requieren para calcular: f(5)? f(4)? f(3)? f(2)? f(6)?
(Gp:) f(5) (Gp:) f(3) (Gp:) f(1) (Gp:) f(2) (Gp:) f(4) (Gp:) f(2) (Gp:) f(3) (Gp:) f(1) (Gp:) f(2)
–> 9 –> 5 –> 3 –> 1 –> 15 Relación: El término T(n) requiere T(n-1)+T(n-2)+1 términos para calcularse.
Análisis de Fibonacci Si el término T(n) requiere T(n-1)+T(n-2)+1 términos para calcularse… se puede decir que T(n) > 2 * T(n-2) … y por lo tanto: T(n) > 2 * 2 * T(n-4) … y T(n) > 2 * 2 * 2 * T(n-6) … y así sucesivamente hasta: T(n) > 2 * 2 * 2 * …. * 2 * T(1) (Gp:) n/2 veces
Por lo tanto: T(n) > 2n/2 y podemos decir que el orden del algoritmo es O(2n/2)
| Página siguiente |