Bloque 1: Introduccion
Unidad 3: Análisis de
algoritmos (parte I)
Departamento de Sistemas Informáticos y Programación
Universidad Complutense de Madrid
Introducción
 El análisis de algoritmos consiste en determinar las
funciones tn que describen alguna propiedad de interés,
habitualmente
 Tiempo consumido
 Espacio utilizado
 Etc. (casos particulares)
 El análisis posee dos perspectivas distintas
 Cómo debe realizarse, esto es, cómo determinar las funciones tn
 Qué tipo de análisis es conveniente realizar, esto es, desde qué
punto de vista deseamos conocer una determinada propiedad
del algoritmo
Se describirá en la Parte II de la presente unidad didáctica
MTP: Metodología y Tecnología de la Programación
2
Determinación de las funciones tn
 Lamentablemente, no existe una fórmula o
procedimiento de tipo general que permita identificar las
funciones tn de un algoritmo
 La identificación exitosa de dichas funciones es altamente
heurística y depende, en gran medida, de la experiencia
 En general, para identificar la función tn, deberemos
 Identificar la operación básica de interés
Recordemos que una operación básica es aquella tal que el
trabajo total realizado por el algoritmo (en tiempo o espacio)
es proporcional al número de veces que se ejecuta dicha
instrucción
 Identificar el parámetro “n” de entrada
 Analizar, desde dentro hacia fuera, las estructuras de control que
producen la ejecución repetida de dicha operación básica
MTP: Metodología y Tecnología de la Programación
3
Ejemplo
n
function busquedaLineal(a:array[1..n] of integer; x:integer):integer;
var
i:integer;
begin
i := 1;
while i <= n and a[i] <> x do
Posibles operaciones básicas
i:= i+1;
if i > n
then busquedaLineal:= 0
else busquedaLineal:= i
end;
Estructuras de control involucradas
MTP: Metodología y Tecnología de la Programación
4
Análisis en función de las estructuras de control
Se deben considerar
Instrucciones simples
Secuencia
Estructuras de control
Alternativas
 If
 Switch
Repetitivas
 For
/ While / Repeat
Invocación procedimental
MTP: Metodología y Tecnología de la Programación
5
Análisis: Secuencia
 Una instrucción cualquiera tiene una complejidad
 tn (instrucción) = 1 si
 Coindice con la operación básica y
 No es una estructura de control o invocación procedimental
 En caso contrario, tn (instrucción) = 0 (en realidad, es una constante de
valor más o menos alto, pero no es relevante a efectos de análisis
 Un bloque de código de la forma:
BEGIN
instrucción-1;
instrucción-2;
...
instrucción-n
END;
tiene como t’n (bloque) = t’n (instrucción-1)+
t’n (instrucción-2)+...
t’n (instrucción-n)
MTP: Metodología y Tecnología de la Programación
6
Análisis: Alternativa (IF)
 Una alternativa (IF) tiene la forma:
IF condicion
then accion-then
else accion-else;
tn (IF) = max{t’n (condicion) + t’n(acción-then),
t’n (condicion) + t’n(acción-else)}
MTP: Metodología y Tecnología de la Programación
7
Ejemplo
 Marcamos con
la operación básica
if i > n
then busquedaLineal:= 0
else busquedaLineal:= i
tn (IF) = max{t’n (condicion) + t’n(acción-then),
t’n (condicion) + t’n(acción-else)} =
max{t’n (i > n) + t’n(busquedaLineal:= 0),
t’n (i > n) + t’n(busquedaLineal:= i)} =
max{1 + 0,
1 + 0} = 1
MTP: Metodología y Tecnología de la Programación
8
Análisis: Alternativa (SWITCH)
 Es similar a un IF. Se indica únicamente por claridad
 Una alternativa (SWITCH) tiene la forma:
SWITCH condicion OF
caso-1: bloque-1;
caso-2: bloque-2;
...
caso-n: bloque-n;
else accion-else
END;
tn (IF) = max{t’n (condicion) + max{t’n(bloque-i)},
t’n (condicion) + t’n(acción-else)}
MTP: Metodología y Tecnología de la Programación
9
Análisis: Repetitivas (FOR/WHILE/REPEAT)
 Son reducibles a bucles WHILE
 Únicamente se estudiará este caso
 Un bucle (WHILE) tiene la forma:
WHILE condicion DO
BEGIN
bloque
END;
tn (WHILE) = iteracciones * (t’n(condicion) + t’n(bloque))
 Nótese que “iteracciones” puede o no depender de n, por lo que esta
expresión es simplicifable
MTP: Metodología y Tecnología de la Programación
10
Ejemplo
Marcamos con
básica
la operación
function busquedaLineal(a:array[1..n] of integer; x:integer):integer;
var
i:integer;
begin
...
while i <= n and a[i] <> x do
i:= i+1;
tn (WHILE) = iteracciones * (t’n(condicion) + t’n(bloque)) =
MTP: Metodología y Tecnología de la Programación
n
* (t’n(i
<= n and a[i] <> x)
n
* (0 + 1) = n
+ t’n(i:=
i+1))
=
11
Análisis: Invocación procedimental
 Una invocación procedimental implica la ejecución de un
subprograma
 Hay que distinguir dos casos
 El subprograma no es directa o indirectamente recursivo
tn (invocación) = t’n(subprograma)
 El programa es directa o indirectamente recursivo
Realizar un análisis del subprograma utilizando técnicas de
recurrencia
MTP: Metodología y Tecnología de la Programación
12
Ejemplo
 Las operaciones básicas están dentro de ambos
subprogramas (cada uno tendrá una operación básica
particular)
function previofactorial (a:array[1..k], i:integer):integer;
var n:integer;
begin
n := busquedaLineal(a, i);
previoFactorial := factorial(n)
end;
tnk (previofactorial) = t’k (busquedaLineal) + t’n(factorial) =
k + t’k(factorial), siendo
t’k(factorial) = 1+t’k-1(factorial) y
t’k = k
MTP: Metodología y Tecnología de la Programación
t’1= 1
13
Notas finales
 En ocasiones, no se busca determinar la complejidad
temporal o espacial del algoritmo, sino la función de
complejidad de alguna operación particular
 Ejemplo: Numero de comparaciones
 Solución: Varias operaciones básicas
function busquedaLineal(a:array[1..n] of integer; x:integer):integer;
var
i:integer;
begin
i := 1;
while i <= n and a[i] <> x do
i:= i+1;
if i > n
then busquedaLineal:= 0
else busquedaLineal:= i
end;
 tn = 2n+1
MTP: Metodología y Tecnología de la Programación
14
Notas finales: Utilización de un testigo
 Una alternativa al análisis puramente teórico del algoritmo es la
utilización de un testigo o barómetro
 Por ejemplo:
function busquedaLineal(a:array[1..n] of integer; x:integer):integer;
var
i:integer;
begin
i := 1;
while i <= n and a[i] <> x do begin
i:= i+1;
WRITE(‘*’)
end;
if i > n
then busquedaLineal:= 0
else busquedaLineal:= i
end;
 Tiene el inconveniente de que no deduce la expresión analítica de la
función de complejidad
 Hay soluciones
MTP: Metodología y Tecnología de la Programación
15
Notas finales: Utilización de un testigo
 Utilizando un testigo, y tabulando los resultados (numero
de iteracciones) para distintos valores de n, se pueden
identificar funciones que definen conjuntos O,  y, en
algunos casos,  , a los que pertenece la función de
complejidad del algoritmo
 La estrategia es calcular los valores iteracciones/f(n),
siendo f(n) una o varias funciones (por ejemplo, las
funciones destacadas) de interés
 Si:
 iteracciones/f(n) tiende a un valor constante, la función de
complejidad del algoritmo es (f(n))
 iteracciones/f(n) tiende a 0, la función de complejidad del
algoritmo es O(f(n))
 iteracciones/f(n) tiende a infinito, la función de complejidad del
algoritmo es (f(n))
MTP: Metodología y Tecnología de la Programación
16
Notas finales
 Existen dos casos en que la estrategia enunciada NO FUNCIONA
 CASO 1: Que la operación básica no refleje, realmente, el trabajo
realizado por el algoritmo (inadvertidamente)
 Ejemplo:
function Fibiter (n:integer):integer;
var i,j, k:integer;
begin
Las operaciones de suma
i:=1;j:=0;k:=1;
pueden consumir un tiempo
while k<= n do begin
proporcional a n (suponer,
j:=i+j;
i:=j-i;
por ejemplo, aritmética entera
k:= k+1
exacta, aumentando
end;
la función de complejidad dell
Fibiter:= j
algoritmo
end;
 Solución: re-considerar la operación básica, considerar varias
operaciones básicas, suponer invocación procedimental
MTP: Metodología y Tecnología de la Programación
17
Notas finales
 Habitualmente, tn se identifica para el CASO PEOR de la
ejecución de una determinada función
 Los conceptos de todos los casos, caso mejor, caso medio y
caso peor se estudiarán más adelante
 No obstante, en algunos casos el análisis del CASO
PEOR es excesivamente pesimista
 Incluso para el caso peor
 Aumenta considerablemente el orden de las funciones de
complejidad
 Concretamente, en ciertas ocasiones, es necesario
aplicar un análisis amortizado en las invocaciones
procedimentales
 Lo estudiaremos más adelante
MTP: Metodología y Tecnología de la Programación
18
Notas finales
 Por último, es conveniente señalar que, salvo casos
extraordinarios en los que estemos interesados en las
funciones tn concretas, utilizaremos los conjuntos O,  y
 deducibles a partir de tn
 Normalmente, utilizaremos alguna de las funciones
destacadas 1, log n, n, n log n, n2, nk, an, bn, n!
 Se podrán deducir las funciones concretas a partir de las
propiedades de los conjuntos O,  y  y de la
experiencia
MTP: Metodología y Tecnología de la Programación
19
Descargar

Document