Eficiencia de los Algoritmos Computacionales (página 2)

Partes: 1, 2

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)