ALGORITMICA III

ANALISIS DE COMPLEJIDAD
ALGORITMICA ITERATIVA CON
NOTACION ASINTOTICA

Docente: Carlos A. Ruiz De La Cruz Melo

Correo: [email protected]
NOTACION ASINTOTICA
El anlisis de los algoritmos que hemos realizado
hasta aqu es muy preciso pero resulta incomodo
para entender que tan eficiente es un algoritmo o
para poder compararlo contra otro algoritmo.

Habitualmente no interesa cuanto tarda

exactamente un algoritmo sino que nos interesa
saber cual es la tasa de crecimiento del algoritmo en
funcin de los datos de entrada.

Para el estudio de algoritmos existe una notacin

muy practica y utilizada universalmente en este tipo
de problemas conocida como la gran O, notacin
asinttica que define el orden de un algoritmo o
Tasa de crecimiento del tiempo que insume el
algoritmo en funcin de la cantidad o tamao de los
datos de entrada.
NOTACION ASINTOTICA
La eficiencia asinttica del
algoritmo. Se denomina
asinttica porque analiza el
comportamiento de las
funciones en el lmite, es decir,
su tasa de crecimiento.

El lmite de una funcin f(x), cuando x tiende a c es L si y slo si

para todo >0 existe un >0 tal que para todo nmero real x en
el dominio de la funcin

0 x c f ( x) L
NOTACION ASINTOTICA

La notacin asinttica se describe por medio

de una funcin cuyo dominio es la de los
nmeros naturales (N ) estimado a partir del
tiempo de ejecucin o del espacio de
memoria en base a la longitud de la entrada

La notacin asinttica captura el

comportamiento de la funcin para
valores grandes de N.
ORDENES DE COMPLEJIDAD
La mejor tcnica para diferenciar la
eficiencia de los algoritmos es el
estudio de los rdenes de
complejidad.

El orden de complejidad se
expresa generalmente en trminos
de la cantidad de datos procesados
por el programa, denominada n, que
puede ser el tamao dado o
estimado.
Funciones conocidas
n log2n n nlog2n n2 n3 2n

5 3 5 15 25 125 32
10 4 10 40 100 1000 1000
100 7 100 700 10000 106 1030

1000 10 1000 10000 106 109 10300

TIEMPOS DE EJECUCIN
DE 4 PROGRAMAS

Tiempo Tamao Tamao Incremento

Ejecucin mximo del mximo del en los datos
t(n) problema para problema para del problema
103 segundos 104 segundos

100n 10 100 1000 (900%) t(n)

5n2
5n2 14 45 320 (220%) 2n
n3/2
100n
n3/2 12 27 230 (130%)
2n 10 13 130 (30%)

n
ALGUNOS ORDENES DE
COMPLEJIDAD

O(1) orden constante

O(log n) orden logartmico
O(n) orden lineal
O(n2 ) orden cuadrtico
O(na) orden polinomial (a > 2)
O(an) orden exponencial (a > 2)
O(n!) orden factorial
GRAFICA DE FUNCIONES
Funciones que se utilizan
habitualmente a la hora de describir el
coste de los algoritmos
ALGORITMO ACEPTABLE
Para considerar que el coste de un
algoritmo es computacionalmente
aceptable este debe ser, como
mucho , de orden polinmico y con
un grado no demasiado elevado.

Algoritmos con una tasa de

crecimiento superior, por ejemplo
exponencial, se convierten en
soluciones teoricas pero que no se
pueden usar en la practica porque
solo obtienen resultados cuando el
tamao de los datos es muy
pequeo
 NOTACIN ASINTTICA O
Sea t, f: N R+ funciones.

Diremos que t(n) est en el orden de f(n), si

t(n) est acotada superiormente por un
mltiplo real positivo de f(n) para todo n
bien grande.

Existe c y un valor en el umbral no tal

que t(n) cf(n) siempre que n >= no
Adems, t(n) O(f(n)) O grande de
f(n).

O f n t : N R / c R , n N / t n c * f n , n 0 N / n n 0
0 0

NOTACIN ASINTTICA O
Consideremos las funciones f(n) = log2n y g(n) = (n/4)2 .
NOTACIN ASINTTICA O

As, decir que el tiempo de ejecucin T(n) de un algoritmo es

O(n2), que se lee o mayscula de n al cuadrado o tan slo
o de n cuadrado, significa que existen constantes positivas
c y n0 tales que para n mayor o igual que n0, se tiene que:

T(n)cn2.

Dicho de otro modo, cuando el tiempo de ejecucin de un

programa es O(f(n)), se dice que tiene una velocidad de
crecimiento f(n)
IMPACTO PRACTICO
Sea un problema que sabemos resolver con
algoritmos de diferentes complejidades. Para
compararlos entre si, supongamos que todos ellos
requieren 1 hora de ordenador para resolver un
problema de tamao N=100.

Qu ocurre si
O(f(n)) N=100 t=2h N=200
disponemos
log n 1h 10000 1.15 h
del doble de
tiempo o el n 1h 200 2h

doble de los n log n 1h 199 2.30 h

datos? . n2 1h 141 4h
n3 1h 126 8h
2n 1h 101 1030 h
Impacto Practico
Los algoritmos de tipo polinmico no son
una maravilla, y se enfrentan con
dificultad a problemas de tamao
creciente. La prctica viene a decirnos
que son el lmite de lo "tratable".

Mientras complejidades del orden O(n2) y

O(n3) suelen ser efectivamente
abordables, prcticamente nadie acepta
algoritmos de orden O(n100), por muy
polinmicos que sean.

Cualquier algoritmo por encima de una

complejidad polinmica se dice
"intratable" y slo ser aplicable a
problemas ridiculamente pequeos.
IMPACTO PRACTICO
Por ejemplo, si disponemos de
dos algoritmos para el mismo
problema, con tiempos de
ejecucin respectivos:

asintticamente, "f" es mejor

algoritmo que "g"; pero esto es
cierto a partir de N > 100.

Si nuestro problema no va a
tratar jams problemas de
tamao mayor que 100, es
mejor solucin usar el
algoritmo "g

algoritmo tiempo complejidad

f 100 n O(n)
g n2 O(n2)
IMPACTO PRACTICO

an siendo dos algoritmos con idntico

comportamiento asinttico, es obvio que el
algoritmo "f" es siempre 100 veces ms
rpido que el "g" y candidato primero a ser
utilizado.

algoritmo tiempo complejidad

f n O(n)
g 100 n O(n)
IMPACTO PRACTICO
si un programa se va a ejecutar muy
pocas veces, los costes de codificacin y
depuracin son los que ms importan,
relegando la complejidad a un papel
secundario.

si a un programa se le prev larga vida,

hay que pensar que le tocar mantenerlo
a otra persona y, por tanto, conviene
tener en cuenta su legibilidad, incluso a
costa de la complejidad de los algoritmos
empleados.

si podemos garantizar que un programa

slo va a trabajar sobre datos pequeos
(valores bajos de N), el orden de
complejidad del algoritmo que usemos
suele ser irrelevante, pudiendo llegar a
ser incluso contraproducente.
Propiedades de la Notacin O

f n
Lim R 0 f n g n y g n f n
n g n

f n
Lim 0 f n g n pero g n f n
n g n

f n
Lim f n g n y g n f n
n g n
Es cierta la siguiente
afirmacin?
Aplicando LHospital
n2O(n3) repetidas veces

Solucin

Lim(n2/n3)=lim 2n/3n2 =2/6n=0/6=0

n n

Por
f n
Lim 0 f n g n pero g n f n
n g n

n2O(n3)
Es cierta la siguiente
afirmacin?
n3O(n2)
Solucin

Lim(n3/n2)=lim n =
n n

Por
f n
Lim f n g n y g n f n
n g n

n3O(n2)
REGLAS PRCTICAS PARA
CALCULAR LA COMPLEJIDAD

Los algoritmos bien estructurados combinan

las sentencias de alguna de las formas
siguientes

1. sentencias sencillas
2. secuencia (;)
3. decisin (if)
4. bucles
5. llamadas a procedimientos
REGLAS PRCTICAS
Sentencias sencillas

Nos referimos a las sentencias

de asignacin, entrada/salida,
etc. siempre y cuando no
trabajen sobre variables
estructuradas cuyo tamao
este relacionado con el
tamao N del problema.

La inmensa mayora de las

sentencias de un algoritmo
requieren un tiempo
constante de ejecucin,
siendo su complejidad O(1).
REGLAS PRCTICAS
Secuencia (;)

La complejidad de una serie de

elementos de un programa es
del orden de la suma de las
complejidades individuales,
aplicndose las operaciones
arriba expuestas.
REGLAS PRCTICAS
Decisin (if)

La condicin suele ser

de O(1), complejidad a
sumar con la peor
posible, bien en la
rama THEN, o bien en
la rama ELSE. En
decisiones multiples
(ELSE IF, SWITCH
CASE), se tomara la
peor de las ramas.
REGLAS PRCTICAS
Bucles

En los bucles con contador

explcito, podemos
distinguir dos casos, que el
tamao N forme parte de
los lmites o que no.

Si el bucle se realiza un
nmero fijo de veces,
independiente de N,
entonces la repeticin slo
introduce una constante
multiplicativa que puede
absorberse. for (int i= 0; i < K; i++) {
algo_de_O(1)
}

K*O(1) = O(1)
Reglas Prcticas
Bucles
Si el tamao N aparece como lmite de
iteraciones

a) for (int i= 0; i < N; i++) {

algo_de_O(1)
}

N * O(1) = O(n)

b) for (int i= 0; i < N; i++) {

for (int j= 0; j < N; j++) {
algo_de_O(1)
}
}

Tendremos N * N * O(1) = O(n2)

Reglas Prcticas
Bucles

for (int i= 0; i < N; i++) {

for (int j= 0; j < i; j++) {
algo_de_O(1)
}
}

el bucle exterior se realiza N veces, mientras que el interior se

realiza 1, 2, 3, ... N veces respectivamente.

En total, 1 + 2 + 3 + ... + N = N*(1+N)/2 O(n2)

Reglas Prcticas
A veces aparecen bucles
multiplicativos, donde la evolucin c= 1;
de la variable de control no es lineal
while (c < N) {
(como en los casos anteriores)
algo_de_O(1)
c= 2*c;
El valor incial de "c" es 1, siendo
}
"2k" al cabo de "k" iteraciones.

El nmero de iteraciones es tal que

2k >= N => k= (log2 (N)) [el entero
inmediato superior] y, por tanto, la
c= 2x1 = 2.. 21
complejidad del bucle es
c=2x2= 4.. 22
c=2x4 = 8 23
O(log n).
:
Reglas Prcticas
Un razonamiento c= N;
anlogo nos lleva a while (c > 1) {
log2(N) iteraciones y, algo_de_O(1)
por tanto, a un orden c= c / 2;
O(log n) de complejidad }

tenemos un bucle interno

de orden O(log n) que se
ejecuta N veces, luego el
conjunto es de orden for (int i= 0; i < N; i++) {
O(nlog n) c= i;
while (c > 0) {
algo_de_O(1)
c= c/2;
}
}
Ejercicio 1
Dado el siguiente algoritmo,
determina su complejidad.

funcion valor(n): entero

para i1 hasta N hacer
para j 1 hasta 20 hacer
aux j * 2
aux aux* i + r
finpara
finpara
retornar aux
finvalor
Solucin 1
Dado el siguiente algoritmo, determina su complejidad.

funcion valor(n): entero

para i1 hasta N hacer
para j 1 hasta 20 hacer
aux j * 2
aux aux* i + r
finpara
finpara
retornar aux
finvalor
Ejercicio 2
Dado el siguiente algoritmo, determine su complejidad.

Funcion valor(n): entero

r 1
para i 1 hasta n hacer
para j 1 hasta n hacer
si i < j entonces
aux i + j
sino
auxi - j
finsi
finpara
finpara
retornar aux
finvalor
Solucin 2
Dado el siguiente algoritmo, determina su complejidad.
Funcion valor(n): entero
r 1
para i 1 hasta n hacer
para j 1 hasta n hacer
si i < j entonces
aux i + j
sino
auxi - j
finsi
finpara
finpara
retornar aux
finvalor
Ejercicio 3
Dado el siguiente algoritmo,
determine su complejidad.

funcion valor(n): entero

desde i1 hasta n hacer
desde j 1 hasta i hacer
si i < j entonces
aux i + j
si i + 2 < j entonces
aux aux * 2
finsi
finsi
finpara
finpara
retornar a ux
finvalor
Solucin 3
Dado el siguiente algoritmo, determina su complejidad.

funcion valor(n): entero

desde i1 hasta n hacer
desde j 1 hasta i hacer
si i < j entonces
aux i + j
si i + 2 < j entonces
aux aux * 2
finsi
finsi
finpara
finpara
retornar aux
finvalor
Ejercicio 4
Calcular sus tiempos de ejecucin en el
mejor, peor, y caso medio.

para i1 hasta n-1 hacer (* 1 *)

para jn hasta i+1 paso -1 hacer (* 2 *)
if a[j-1]>a[j] entonces (* 3 *)
tempa[j-1] (* 4 *)
a[j-1]a[j] (* 5 *)
a[j]temp (* 6 *)
fin (* 7 *)
fin (* 8 *)
fin
Solucin 4:
Se calcula primero el nmero de
operaciones elementales (OE) que
se realizan:

En la lnea (1) se ejecutan 3 OE

(una asignacin, una resta y una
comparacin) en cada una de las para i1 hasta n-1 hacer (* 1 *)
iteraciones del bucle ms otras 3 al para jn hasta i+1 paso -1 hacer (* 2 *)
final, cuando se efecta la salida if a[j-1]>a[j] entonces (* 3 *)
del para. tempa[j-1] (* 4 *)
Igual ocurre con la lnea (2), a[j-1]a[j] (* 5 *)
tambin con 3 OE (una asignacin, a[j]temp (* 6 *)
una suma y una comparacin) por
fin (* 7 *)
iteracin, ms otras 3 al final del
bucle. fin (* 8 *)
En la lnea (3) se efecta una fin
condicin, con un total de 4 OE
(una diferencia, dos accesos a un
vector, y una comparacin).
Las lneas (4) a (6) slo se
ejecutan si se cumple la condicin
de la lnea (3), y realizan un total
de 9 OE: 3, 4 y 2 respectivamente.
MEJOR CASO
En el caso mejor para el
algoritmo la condicin de la para i1 hasta n-1 hacer (* 1 *)
lnea (3) ser siempre falsa, y para jn hasta i+1 paso -1 hacer (* 2 *)
no se ejecutarn nunca las if a[j-1]>a[j] entonces (* 3 *)
lneas (4), (5) y (6). As, el bucle tempa[j-1] (* 4 *)
ms interno realizar (ni) a[j-1]a[j] (* 5 *)
iteraciones, cada una de ellas a[j]temp (* 6 *)
con 4 OE (lnea 3), ms las 3 fin (* 7 *)
OE de la lnea (2). Por tanto, el fin (* 8 *)
bucle ms interno realiza un fin
total de

OE, siendo el 3 adicional por la

condicin de salida del bucle.
MEJOR CASO

A su vez, el bucle externo para i1 hasta n-1 hacer (* 1 *)

repetir esas 7(ni)+3 OE para jn hasta i+1 paso -1 hacer (* 2 *)
en cada iteracin, lo que if a[j-1]>a[j] entonces (* 3 *)
hace que el nmero de OE tempa[j-1] (* 4 *)
que se realizan en el a[j-1]a[j] (* 5 *)
algoritmo sea: a[j]temp (* 6 *)
fin (* 7 *)
fin (* 8 *)
fin
PEOR CASO para i1 hasta n-1 hacer (* 1 *)
para jn hasta i+1 paso -1 hacer (* 2 *)
En el caso peor, la condicin de if a[j-1]>a[j] entonces (* 3 *)
la lnea (3) ser siempre tempa[j-1] (* 4 *)
verdadera, y las lneas (4), (5) y a[j-1]a[j] (* 5 *)
(6) se ejecutarn en todas las a[j]temp (* 6 *)
iteraciones. Por tanto, el bucle fin (* 7 *)
ms interno realiza fin (* 8 *)
fin

OE. El bucle externo realiza

aqu el mismo nmero de
iteraciones que en el caso
anterior, por lo que el nmero de
OE en este caso es:
CASO MEDIO para i1 hasta n-1 hacer
para jn hasta i+1 paso -1 hacer
(* 1 *)
(* 2 *)
if a[j-1]>a[j] entonces (* 3 *)
En el caso medio, la condicin tempa[j-1] (* 4 *)
de la lnea (3) ser verdadera a[j-1]a[j] (* 5 *)
con probabilidad 1/2. As, las a[j]temp (* 6 *)
lneas (4), (5) y (6) se ejecutarn fin (* 7 *)
en la mitad de las iteraciones del fin (* 8 *)
bucle ms interno, y por tanto fin
realiza

OE. El bucle externo realiza

aqu el mismo nmero de
iteraciones que en el caso
anterior, por lo que el nmero
de OE en este caso es:
NOTACIN ASINTTICA
Sea t, f: N R+ funciones.

Diremos que t(n) est en Omega de f(n),

si t(n) est acotada inferiormente por un
mltiplo real positivo de f(n) para todo n
bien grande.

Existe d y un valor en el umbral no tal

que t(n) >= df(n) siempre que n >= no
Adems, t(n) W(f(n)) W grande
de f(n).

Wf n t : N R 0 / d R 0 , n N / t n d * f n , n 0 N / n n 0

NOTACIN ASINTTICA W
Consideremos las funciones f(n) = log2n y g(n) = (n/4)2 .

t(n)

g(n) =(n/4)2

f(n)=Log2n
(n/4)2 WLog2n)

n
a b
NOTACIN ASINTTICA

La funcin omega grande, se utiliza

para especificar una cota inferior para
la velocidad del crecimiento, de una
funcion F(n) cuando esta en funcion de
n.

La cota inferior asinttica tiene utilidad

en Teora de la complejidad
computacional a la hora de calcular la
complejidad del mejor caso para los
algoritmos.
PROPIEDADES DE LA NOTACIN W

f n
Lim R 0
f n Wg n y g n W f n
n g n

f n
Lim 0 f n Wg n pero g n W f n
n g n

f n
Lim f n Wg n y g n W f n
n g n
Ejercicio 5
Determinar costo de ejecucin

funcion MXIMO ( v, n) : entero

entero: i, max

maxv[1]
para i 2 hasta n hacer
si v[i]>max entonces
max v[i]
finsi
finpara n
retornar max Ci 1 1 1 (n 2 1) n W(n)
finMAXIMO i 2 (n)
n
Cs 1 2 1 (n 2 1).2 2n 1(n)
i 2
NOTACIONES ASINTTICAS

Notacin Theta(): Entonces t(n)

est en Theta de f(n) si y solo s t(n)
est en Orden exacto de f(n) y t(n)
est en Omega de f(n).

Adems lo denotamos t(n) (f(n))

grande de f(n).

f n t : N R / c , d R , n N / c * f n t n d * f n , n 0 N / n n 0
0 0

PROPIEDADES DE LA NOTACIN

f n 0
Lim R f n g n y f n Wg n f n g n
n g n

f n
Lim 0 f n g n y f n Wg n f n g n
n g n

f n
Lim f n g n y f n Wg n f n g n
n g n
RELACIONES ENTRE O W

Notacin O (big-omicron) caso peor

Notacin (omega) caso mejor
Notacin (big-theta) caso promedio
EJERCICIO DE LABORATORIO

En los algoritmos de clasificacin iterativos y bajo

arreglos:

Ordenacion Burbuja
Ordenacion por insercion

1. Encuentre el caso medio, el peor y mejor caso

2. Luego implemente ambos algoritmos en C++ y

java. Pruebe cada programa tanto con datos
ordenados, desordenados aleatoriamente y en
sentido inverso y no se olvide para cada caso
tomar tiempos.

3. Despus verifique si existe alguna relacin entre

sus ecuaciones halladas para el caso medio, peor
y mejor caso) con los tiempos reales de sus
implementaciones en java y C++.