PDF de programación - Algorítmica (1): Análisis de complejidad

Algor´ıtmica (1): An´alisis de complejidad

Dr. J.B. Hayet

CENTRO DE INVESTIGACI ´ON EN MATEM´ATICAS

Septiembre 2013

J.B. Hayet

Programaci´on, Septiembre 2013

,

1 / 43

Outline

1 Complejidad y notaci´on asint´otica

2 Analisis de complejidad

J.B. Hayet

Programaci´on, Septiembre 2013

,

2 / 43

Complejidad y notaci´on asint´otica

Outline

1 Complejidad y notaci´on asint´otica

2 Analisis de complejidad

J.B. Hayet

Programaci´on, Septiembre 2013

,

3 / 43

Complejidad y notaci´on asint´otica

Complejidad

Para poder caracterizar implementaciones: aislar la o las
“variables” que permiten caracterizar la complejidad del
problema que resolver, para expresar la complejidad de los
operaciones. T´ıpicamente, un numero de elementos dentro del
contenedor. . .

Ejemplos:
Pila.
Cadena de caracteres.
Grafo.

J.B. Hayet

Programaci´on, Septiembre 2013

,

4 / 43

Complejidad y notaci´on asint´otica

Complejidad en espacio

La primera manera de caracterizar una implementaci´on es en
t´erminos de la memoria que requiere (espacio): una funci´on
M(n), caracter´ıstica del algoritmo, en funci´on del
tama˜no de los datos (n), que permite evaluar la cantidad
de memoria requerida para usar el algoritmo.

J.B. Hayet

Programaci´on, Septiembre 2013

,

5 / 43

Complejidad y notaci´on asint´otica

Complejidad en tiempo

Es una funci´on T (n) que describe el comportamiento del
algoritmo en cuanto a su tiempo de ejecuci´on, en t´erminos
de n, el tama˜no de los datos de input al algoritmo. . .

Se expresa esta funci´on T (n) de manera exacta si posible, en
t´erminos de las operaciones elementales (operaciones
aritm´eticas, operaciones de asignaci´on, de dereferenciaci´on), y no en
t´erminos de tiempo absoluto. . . Lo que nos interesa es la tasa de
crecimiento, la tendencia cuando n es grande.

J.B. Hayet

Programaci´on, Septiembre 2013

,

6 / 43

Complejidad y notaci´on asint´otica

Complejidad en tiempo

Aunque una operaci´on elemental puede ser m´as costosa en tiempo
que otra, por ejemplo, no considerar la constante multiplicativa que
hay entre los dos. En cambio, se considera la complejidad en
terminos de n´umero total de operaciones elementales.
v o i d Ex1 ( i n t n ) {

i , j ;

i n t
i n t sum=0,summ=0, l i m i t=n∗n ;
f o r

( i =1; i <l i m i t ; i ++)

++sum

f o r

( j =1; j <sum ; j ++)

++summ ;

}

J.B. Hayet

Programaci´on, Septiembre 2013

,

7 / 43

Complejidad y notaci´on asint´otica

Complejidad en tiempo

En el ejemplo:

T (n) = 4 + 1 + n2 + 2(n2 − 1) + 1 + n2 − 1 + 2(n2 − 2)

= 6n2 − 1

Aqu´ı lo que nos importa realmente es sobre todo que se
comporta como n2 para grandes valores de n.

J.B. Hayet

Programaci´on, Septiembre 2013

,

8 / 43

Complejidad y notaci´on asint´otica

Complejidad en tiempo

A veces no se puede establecer una forma exacta o aun aproximada
de T (n), sino expresarla estad´ısticamente:

en promedio
en el peor de los casos

Ejemplo: b´usqueda en un quadtree.

J.B. Hayet

Programaci´on, Septiembre 2013

,

9 / 43

Complejidad y notaci´on asint´otica

Gran O

Como lo que nos interesa es el comportamiento asint´otico de
las complejidades, se usa herramientas para comparar esos
comportamientos cuando n → ∞.
Dadas dos funciones T y U de N en R, se dice que
T (n) = O(U(n)) ssi existe un real c > 0 y un entero n0
tal que ∀n ≥ n0, T (n) ≤ cU(n)

U (n)

T (n)

J.B. Hayet

Programaci´on, Septiembre 2013

,

10 / 43

Complejidad y notaci´on asint´otica

Gran O

8n

2n + 4

n

T (n) = 2n + 4 = O(n)

4n

2n + 4

n

J.B. Hayet

Programaci´on, Septiembre 2013

,

11 / 43

Complejidad y notaci´on asint´otica

Gran O

La notaci´on gran O define una cuota superior a una
funci´on y una familia de tendencia de crecimiento.
T (n) = O(U(n)) significa que el crecimiento de T es
inferior o igual al de U para grandes valores de n.
Se puede comparar funciones:

1 ≤ log n ≤ n ≤ n log n ≤ n2 ≤ 2n ≤ nn.

Las constantes multiplicativas no cuentan.

J.B. Hayet

Programaci´on, Septiembre 2013

,

12 / 43

Complejidad y notaci´on asint´otica

Gran O

Si T (n) es un polinomio de grado g , T (n) = O(ng ): se
puede “olvidar” los t´erminos de grado inferior y las constantes.
Usar la clase de funciones m´as chica: 2n es O(n) (no se
dice, aunque es cierto, que es O(n2)).
Usar la expresi´on mas simple: no se dice que 2n es 1

2n.

J.B. Hayet

Programaci´on, Septiembre 2013

,

13 / 43

Complejidad y notaci´on asint´otica

Gran O

Propiedad: suma y producto.
Si T1(n) = O(U1(n)) y T2(n) = O(U2(n)), entonces
T (n) = T1(n) + T2(n) = O(max(U1(n), U2(n))).
Si T1(n) = O(U1(n)) y T2(n) = O(U2(n)), entonces
T (n) = T1(n)T2(n) = O(U1(n)U2(n)).

J.B. Hayet

Programaci´on, Septiembre 2013

,

14 / 43

Complejidad y notaci´on asint´otica

Gran O

Propiedad: suma y producto.
Si T1(n) = O(U1(n)) y T2(n) = O(U2(n)), entonces
T (n) = T1(n) + T2(n) = O(max(U1(n), U2(n))).
Si T1(n) = O(U1(n)) y T2(n) = O(U2(n)), entonces
T (n) = T1(n)T2(n) = O(U1(n)U2(n)).

0) / ∀n ≥ n1
0) / ∀n ≥ n2

0, T1(n) ≤ c1U1(n)
0, T2(n) ≤ c2U2(n)

Prueba:
∃ (c1 > 0,n1
∃ (c2 > 0,n2
entonces :
∀n ≥ max(n1
∀n ≥ max(n1

0), T (n) ≤ (c1 + c2) max(U1(n), U2(n)) (cid:3)
0), T (n) ≤ c1c2U1(n)U2(n) (cid:3)

0, n2
0, n2

J.B. Hayet

Programaci´on, Septiembre 2013

,

14 / 43

Complejidad y notaci´on asint´otica

Gran O

Propiedad: transitividad.
Si T (n) = O(U(n)), y U(n) = O(W (n)), entonces
T (n) = O(W (n)).

J.B. Hayet

Programaci´on, Septiembre 2013

,

15 / 43

Complejidad y notaci´on asint´otica

Gran O

Propiedad: transitividad.
Si T (n) = O(U(n)), y U(n) = O(W (n)), entonces
T (n) = O(W (n)).

Prueba:
0, T (n) ≤ c1U(n),
∃ (c1 > 0,n1
0) / ∀n ≥ n1
0, U(n) ≤ c2V (n),
∃ (c2 > 0,n2
0) / ∀n ≥ n2
0), T (n) ≤ c1c2V (n) (cid:3)
entonces ∀n ≥ max(n1
0, n2

J.B. Hayet

Programaci´on, Septiembre 2013

,

15 / 43

Complejidad y notaci´on asint´otica

Gran O

Propiedad: base de logaritmo y O.
loga n = O(logb n) para cualquieros a, b > 1. Eso significa que
asintoticamente, no importa la base del logaritmo, de la
misma manera que no importa un factor multiplicativo en una
potencia constante de n. Se podr´a usar base 2, e o 10.

J.B. Hayet

Programaci´on, Septiembre 2013

,

16 / 43

Complejidad y notaci´on asint´otica

Gran O

Propiedad: base de logaritmo y O.
loga n = O(logb n) para cualquieros a, b > 1. Eso significa que
asintoticamente, no importa la base del logaritmo, de la
misma manera que no importa un factor multiplicativo en una
potencia constante de n. Se podr´a usar base 2, e o 10.

Prueba:
loga n = 1

logb a logb n.

J.B. Hayet

Programaci´on, Septiembre 2013

,

16 / 43

Complejidad y notaci´on asint´otica

Gran omega

Se dice que T (n) = Ω(U(n)) ssi existe un real c > 0 y
un entero n0 tal que ∀n ≥ n0, T (n) ≥ cU(n).

Establece una cuota inferior a T (n). Es equivalente a
U(n) = O(T (n)): si existe n0 y c > 0 tal que T (n) ≥ cU(n),
U(n) ≤ 1

c T (n).

Las propiedades de O valen para Ω (transitividad, polinomios,
producto), y el max se hace min en la propiedad relativa a la suma.

J.B. Hayet

Programaci´on, Septiembre 2013

,

17 / 43

Complejidad y notaci´on asint´otica

Gran theta

Se dice que T (n) = Θ(U(n)) ssi T (n) = O(U(n)) y
T (n) = Ω(U(n)).

Establece la equivalencia de comportamiento de dos funciones para
grandes n. Lo que nos interesar´a particularmente es la cuota
superior.

J.B. Hayet

Programaci´on, Septiembre 2013

,

18 / 43

Complejidad y notaci´on asint´otica

Mas propiedades

Se puede escribir que T (n) = O(U(n)) si limn→∞ T (n)
una constante positiva.
Prueba: si el limite es c, existe n0 tal que | T (n)
implica T (n)

U(n) − c| < 1

2 para n ≥ n0,

U(n) < c + 1

U(n) es

2, lo que

T (n) < (

+ c)U(n) (cid:3)

1
2

Se puede escribir que T (n) = Θ(U(n)) si limn→∞ T (n)
constante positiva no nula.
Prueba: igual, pero implica T (n)

(cid:3)

2 , y T (n)

U(n) ≥ c

U(n) ≤ 3c

U(n) es

2

J.B. Hayet

Programaci´on, Septiembre 2013

,

19 / 43

Complejidad y notaci´on asint´otica

Mas propiedades

Dominaciones:

nk = O((1 +
)n)) para todo k > 0 y todo
> 0: un
polinomio es dominado por una exponencial, incluso con una
potencia arbitrariamente peque˜na.
(log n)k = O(n
) para todo k > 0 y todo
> 0: un
logaritmo es dominado por una potencia, incluso de factores
arbitrariamente peque˜nos.

J.B. Hayet

Programaci´on, Septiembre 2013

,

20 / 43

Analisis de complejidad

Outline

1 Complejidad y notaci´on asint´otica

2 Analisis de complejidad

J.B. Hayet

Programaci´on, Septiembre 2013

,

21 / 43

Analisis de complejidad

Analisis: el por qu´e

Antes de optimizar cualquiera cosa en su programa
t´ecnicamente, es importante determinar cual es la complejidad del
algoritmo subyacente!

elecciones algor´ıtmicas cambian el comportamiento
asintotico de la funci´on de complejidad: n, n log n, n2. . .
optimizaciones en el c´odigo “s´olo” cambian constantes o
factores multiplicativos a este comportamiento asint´otico:
n
2 , 4n. . .

J.B. Hayet

Programaci´on, Septiembre 2013

,

22 / 43

Analisis de complejidad

Limites de la an´alisis

A veces se tiene que relativizar las relaciones de dominaci´on
a traves del O: si tengo dos algoritmos para una funcionalidad
dada y que

T (n) = 1000000n
U(n) =

n 12
10 ,

aunque T (n) est´a dominado por U(n), el comportamiento de U
puede ser preferible en la gran mayor´ıa de los casos!

J.B. Hayet

Programaci´on, Septiembre 2013

,

23 / 43

Analisis de complejidad

Ejemplo 1: ordenamiento por selecci´on

Ordenar un arreglo de enteros, por selecci´on: se cambia el valor
examinado por el m´ınimo de los que siguen

index 0 1 2 3 4 5 6 accion
-----------------------------------------------------------------

| 4 0 3 6 1 8 5

it=0 | 0 4 3 6 1 8 5 swap 0,4
it=1 | 0 1 3 6 4 8 5 swap 1,4
it=2 | 0 1 3 6 4 8 5 -
it=3 | 0 1 3 4 6 8 5 swap 4,6
it=4 | 0 1 3 4 5 8 6 swap 5,6
it=5 | 0 1 3 4 5 6 8 swap 6,8

Complejidad?

J.B. Hayet

Programaci´on, Septiembre 2013

,

24 / 43

Analisis de complejidad

Ejemplo 1: ordenamiento por selecci´on

// S e a r c h f o r min between s t a r t and end
i n t m i n I n d e x ( i n t ∗ tab