-
Tema 05: Análisis de algoritmos no recursivos
1
Análisis de algoritmos
M. en C. Edgardo Adrián Franco Martínez http://[email protected]
@edfrancom edgardoadrianfrancom
http://www.eafranco.com/mailto:[email protected]
-
Contenido• Análisis de algoritmos no recursivos• La notación de Landau O
• La notación O• Principio de invarianza del análisis asintótico
• Reglas prácticas del análisis de algoritmos• Ordenes más comunes de los algoritmos• Comportamiento de las funciones• Análisis por bloques de algoritmos iterativos
• Regla 1: Secuencia de instrucciones• Regla 2: Decisiones• Regla 3: Ciclos• Consideraciones especiales
• Logaritmos• Propiedades de los logaritmos
• Ejemplos• Ejemplo 01: Ordenamiento por intercambio• Ejemplo 02: Multiplicación de matrices de n x n• Ejemplo 03: Algoritmo de Horner• Ejemplo 04: Fibonacci (Iterativo)• Ejemplo 05: Búsqueda binaria
2
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
• El análisis de complejidad de los algoritmos norecursivos (iterativos) se realiza bajo los principios delpeor caso y generalmente devolverá la cota superiorajustada del orden de este (O).
• En principio se considera válido cuando solo se deseaobtener una cota para valores grandes de n,basándose en que se cumple el principio deinvarianza del análisis asintótico.
• Para los algoritmos iterativos es únicamente necesarioconocer los órdenes de complejidad O de las tresestructuras de control que todo algoritmo iterativopuede emplear.
Análisis de algoritmos no recursivos
3
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
• Se dice que la función 𝑓(𝑛) “es de orden O𝑔(𝑛)” [O(g(n))], si existen constantes positivas 𝑐y 𝑛0 tales que |𝑓 𝑛 | ≤ 𝑐 |𝑔 𝑛 | cuando 𝑛 ≥𝑛0
• Ejemplos:• n+5 es O(n) pues n+5 ≤ 2n para toda n ≥ 5
• (n+1)2 es O(n2) pues (n+1)2 ≤ 4n2 para n≥ 1
• (n+1)2 NO es O(n) pues para cualquier c > 1 no se cumple que(n+1)2 ≤ c*n
La notación de Landau (O)
4
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
• La notación O proporciona una cota superior para la
tasa de crecimiento de una función.
• La siguiente tabla muestra la relación asintótica de la
notación de orden O.
f(n) es O(g(n)) g(n) es O(f(n))
g(n) crece más Sí No
f(n) crece más No Sí
Igual crecimiento Sí Sí
La notación O
5
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
• Cambios en el entorno HW o SW afectan a factores
constantes pero no al orden de complejidad O(f(n))
• El análisis de la eficiencia es asintótico → sólo es
válido para tamaños de problema suficientemente
grandes lo que hace valido el principio de invarianza.
“Dos implementaciones de un mismo algoritmo no diferirán más que en una constante multiplicativa”
Si f1(n) y f2(n) son los tiempos consumidos por dosimplementaciones de un mismo algoritmo, se verifica que:
Ǝ c, d R,
f1(n) c·f2(n)
f2(n) d·f1(n)
Principio de invarianza del análisis asintótico
6
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
Reglas prácticas del análisis de algoritmos• Operaciones primitivas: tienen complejidad
constante O(1)
• Secuencia de instrucciones: máximo de lacomplejidad de cada instrucción (regla de la suma).
• Condiciones simples: operaciones necesarias paraevaluar la condición más las requeridas paraejecutar la consecuencia (peor caso).
• Condiciones alternativas: operaciones necesariaspara evaluar la condición más las operacionesrequeridas para ejecutar el mayor número deoperaciones de las consecuencias (peor caso).
7
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
8
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
• Bucle con iteraciones fijas: multiplicar el número deiteraciones por la complejidad del cuerpo (regla delproducto).
• Bucle con iteraciones variables: Igual peroponiéndose en el peor caso (ejecutar el mayornúmero de iteraciones posible).
• Llamadas a subprogramas, funciones o métodos:Operaciones de asignación de cada parámetro máslas operaciones de ejecución del cuerpo, más elnúmero de operaciones del retorno.
-
Ordenes más comunes de los algoritmos• O(1) Constante
• O(n) Lineal
• O(n2 ) Cuadrático
• O(n3 ) Cúbico
• O (nm ) Polinomial
• O(log(n)) Logarítmico
• O(nlog(n)) nlog (n)
• O(mn ) exponencial
• O(n!) factorial
9
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
Comportamiento de las funciones
10
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
• El análisis de complejidad por bloques proporciona un
importante medio para hacer un análisis más dinámico,
que se basa principalmente en el conocimiento del
orden de los bloques de instrucciones.
• Un bloque de instrucciones puede ser un algoritmo del
cual conocemos su complejidad computacional. Para
determinar el orden de un bloque, es necesario tener
en mente el orden de las estructuras de control más
usuales.
Análisis por bloques de algoritmos iterativos
11
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
O(g1(n))
O(g2(n))
O(g3(n))
-
• El análisis por bloques implica el análisis de:
1. Secuencias de instrucciones
2. Condicionales
3. Ciclos
12
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
O(g1(n))
O(g2(n))
O(g3(n))
O(g1(n))
O(g2(n))
O(g(n))
-
Regla 1: Secuencia de instrucciones
Ejemplo:• Una secuencia de 3 ciclos:• Ciclo 1 = O(n)• Ciclo 2 = O(log n)• Ciclo 3 = O(n2)
• Tendrá como orden total…• O(n2).
O(g1(n))
O(g2(n))
O(g3(n))
O(gm(n))
≈ O( mayor(g1(n), g2(n), …, gm(n) )
13
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
Regla 2: Decisiones
Ejemplo:
• Una decisión con:• Bloque verdadero= O(n log n)
• Bloque falso= O(log n)
• Tendrá como orden total… • O(n log n).
O(g1(n))
O(g2(n))
≈ O( mayor(g1(n), g2(n)) )
14
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
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
15
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
Consideraciones especiales
• En decisiones y ciclos anidados:• Analizar el código desde la instrucción más
interna hacia el más externa.
• Tips para los ciclos:• ¿“Normalmente” cuál es el orden de la
instrucción interna?
• Si la variable de control se incrementa o decrementocon un valor constante: Orden LINEAL.
• Si la variable de control se multiplica o divide por unvalor constante: Orden LOGARÍTIMICO.
16
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
Ejemplo 01: Ordenamiento por intercambio
for (int i=1; i
-
for (int i=1; i
-
for (int i=1; i
-
20
20
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
Análisis espacial
• 𝑓𝑒 𝑛 = 𝑒𝑠𝑝𝑎𝑐𝑖𝑜 𝑑𝑒 𝑎
• 𝑓𝑒(𝑛) = 𝑛 𝑒𝑠 𝑂(𝑛)
49 12 56 90 2 5 11 32 22 7 99 02 35 1
-
Ejemplo 02: Multiplicación de matrices de n x n
a11 a12 … a1na21 a22 … a2n… … … …
an1 an2 … ann
b11 b12 … b1nb21 b22 … b2n… … … …
bn1 bn2 … bnn
X
c11 = a11*b11+a12 *b21 +…+ a1n *bn1c12 = a11*b12+a12 *b22 +…+ a1n *bn2…
c21 = a21*b11+a22 *b21 +…+ a2n *bn1…
cnn = an1*b1n+an2 *b2n +…+ ann *bnn
c11 c12 … c1nc21 c22 … c2n… … … …
cn1 cn2 … cnn
=
cij = aikbkjn
k=1
21
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
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 ) ←
Complejidad computacional (Edgardo A. Franco) 22
22
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
23
23
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
Análisis espacial
• 𝑓𝑒 𝑛 = 𝑒𝑠𝑝𝑎𝑐𝑖𝑜 𝑑𝑒 𝑛 + 𝑒𝑠𝑝𝑎𝑐𝑖𝑜 𝑑𝑒 (𝐴, 𝐵, 𝐶)
• 𝑓𝑒(𝑛) = 1 + 3𝑛2 𝑒𝑠 𝑂(𝑛2)
3A B C
-
Ejemplo 03: Algoritmo de Horner
24
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
• Sea 𝐴 un vector de coeficientes y sea
𝑃𝑛(𝑧) = σ𝑖=0𝑛 𝐴[𝑖] 𝑧𝑖, un polinomio de grado
𝑛; evaluado para un argumento real 𝑧:
• Encontrar la función complejidad, temporal yespacial, para el algoritmo que evalúa 𝑃𝑛(𝑧).
-
25
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
proc Horner(n,z,A) ´
{
polinomio=0;
for(i=0;i
-
26
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
← O( 1 )
← O( n )
polinomio=0;
for(i=0; i
-
27
27
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
Análisis espacial• 𝑓𝑒 𝑛 = 𝑒𝑠𝑝𝑎𝑐𝑖𝑜 𝑑𝑒 𝑛 + 𝑒𝑠𝑝𝑎𝑐𝑖𝑜 𝑑𝑒 𝑝𝑜𝑙𝑖𝑛𝑜𝑚𝑖𝑜 + 𝑒𝑠𝑝𝑎𝑐𝑖𝑜 𝑑𝑒 𝑧 +𝑒𝑠𝑝𝑎𝑐𝑖𝑜 𝑑𝑒 𝑖 + 𝑒𝑠𝑝𝑎𝑐𝑖𝑜 𝑑𝑒 (𝐴)
• fe(n) = 1 + 1 + 1 + 1 + n = 4 + n 𝑒𝑠 𝑂(𝑛)
n
p
z
i
A
-
Ejemplo 04: Fibonacci (Iterativo)anterior = 1; --> 1 Asignación
actual = 1; --> 1 Asignación
while (n>2){ --> n-2 + 1 Condicionales
aux = anterior + actual; --> n-2 Asignaciones
anterior = actual; --> n-2 Asignaciones
actual = aux; --> n-2 Asignaciones
n = n - 1; --> n-2 Asignaciones
} --> n-2+1 Saltos implicitos
return (actual); --> 1 Asignación
T(n) = 6n-7=O(n)
Complejidad computacional (Edgardo A. Franco) 28
28
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
-
Ejemplo 05: Búsqueda binaria
Complejidad computacional (Edgardo A. Franco) 29
29
An
ális
is d
e al
gori
tmo
s0
5 A
nál
isis
de
algo
ritm
os
no
rec
urs
ivo
sP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
BusquedaBinaria(A,n,dato)
inferior=0;
superior=n-1;
while(inferior