PDF de programación - Algoritmos: Análisis de algoritmos

Algoritmos:

Análisis de algoritmos

Alberto Valderruten

LFCIA - Departamento de Computación

Facultad de Informática

Universidad de A Coruña, España

www.lfcia.org/alg

www.fi.udc.es

Contenido

Análisis de la eficiencia de los algoritmos

Notaciones asintóticas

Cálculo de los tiempos de ejecución

Resolución de recurrencias

Algoritmos - Análisis de algoritmos - 2

1.1 Análisis de la eficiencia de los algoritmos (1)

Objetivo: Predecir el comportamiento del algoritmo

⇒ aspectos cuantitativos:

- tiempo de ejecución
- cantidad de memoria

Disponer de una medida de su eficiencia:

- “teórica”
- no exacta: aproximación suficiente para comparar, clasificar

⇒ acotar T (n): tiempo de ejecución, n = tamaño de la entrada
⇒ T (n) = O(f(n))

n → ∞ : comportamiento asintótico

f(n): una cota superior de T (n) suficientemente ajustada
f(n) crece más deprisa que T (n)

Aproximación?

1. Ignorar factores constantes:

20 multiplicaciones por iteración → 1 operación por iteración
¿cuántas iteraciones? → iteraciones en función de n

2. Ignorar términos de orden inferior: n + cte → n

Algoritmos - Análisis de algoritmos - 3

1.1 Análisis de la eficiencia de los algoritmos (2)

T (n) = O(n) : algoritmo lineal

Ejemplo 1: 2 algoritmos (A1 y A2) para un mismo problema A:
• algoritmo A1: 100n pasos → un recorrido de la entrada
• algoritmo A2: 2n2 + 50 pasos → n recorridos de la entrada
• Comparar : A2 “más lento” que A1, aunque con n ≤ 49 sea más rápido
• Clasificar : lineales, cuadráticos...

T (n) = O(n2) : algoritmo cuadrático
⇒ A1 es mejor

Tasas de crecimiento características:
O(1), O(logn), O(n), O(nlogn), O(n2), O(n3), ...O(2n), ...

Ejemplo 2: aproximación ⇒ limitaciones:

2 algoritmos (B1 y B2) para un mismo problema B:

• algoritmo B1: 2n2 + 50 pasos → O(n2)
• algoritmo B2: 100n1,8 pasos → O(n1,8)

⇒ B2 es “mejor”...
pero a partir de algún valor de n entre 310 y 320 ∗ 106

Algoritmos - Análisis de algoritmos - 4

1.2 Notaciones asintóticas (1)

Objetivo: Establecer un orden relativo entre las funciones,

comparando sus tasas de crecimiento

La notación O:

T (n), f(n) : Z + → R+

Definición:
T (n) = O(f(n)) si ∃ constantes c > 0 y n0 > 0: T (n) ≤ c ∗ f(n) ∀n ≥ n0


n0: umbral
T (n) es O(f(n)), T (n) ∈ O(f(n))
“la tasa de crecimiento de T (n) ≤ que la de f(n)”
→ f(n) es una cota superior de T (n)

Ejemplo: ¿5n2 + 15 = O(n2)?

5n2 + 15 ≤ 6n2 ∀n ≥ 4 (< c, n0 >=< 6, 4 > en la definición)
pero además ∃ infinitos < c, n0 > que satisfacen la desigualdad

Algoritmos - Análisis de algoritmos - 5

1.2 Notaciones asintóticas (2) - La notación O

Observación 1: Según la definición, T (n) podría estar muy por debajo:

¿5n2 + 15 = O(n3)?
5n2 + 15 ≤ 1n3 ∀n ≥ 6 (< c, n0 >=< 1, 6 > en la definición)
pero es más preciso decir = O(n2) ≡ ajustar cotas

⇒ Para el análisis de algoritmos, usar las aproximaciones vistas:

5n2 + 4n → O(n2)
log2n → O(logn)
13 → O(1)
. . .

Observación 2: La notación O también se usa en expresiones como

3n2 + O(n)

Ejemplo 1:

¿Cómo se consigue una mejora más drástica,
- mejorando la eficiencia del algoritmo, o
- mejorando el ordenador?

Algoritmos - Análisis de algoritmos - 6

1.2 Notaciones asintóticas (3) - La notación O

Ejemplo 1 (cont.):

T (n)
log2n
n
nlog2n
n1,5
n2
n3
1, 1n

tiempo1
1000 pasos/s
0,010
1
10
32
1.000
1.000.000
1039

tiempo2
2000 pasos/s
0,005
0,5
5
16
500
500.000
1039

tiempo3
4000 pasos/s
0,003
0,25
2,5
8
250
250.000
1038

tiempo4
8000 pasos/s
0,001
0,125
1,25
4
125
125.000
1038

Tabla: Tiempos de ejecución (en s) para 7 algoritmos de distinta

complejidad (n=1000).

Ejemplo 2: Ordenar 100.000 enteros aleatorios:

- 17 s en un 386 utilizando Quicksort
- 17 min en un procesador 100 veces más rápido utilizando Burbuja

Algoritmos - Análisis de algoritmos - 7

1.2 Notaciones asintóticas (4) - La notación O

Verificación empírica del análisis:

“Método empírico”:

medir tiempos de ejecución (experimentos sistemáticos)
⇒ tabla de tiempos para distintos valores de n
⇒ ¿O?

Método empírico: Renacimiento, s. XVII

“Mide lo que se pueda medir, lo que no se pueda... hazlo medible!”

Verificación empírica: se parte de una función f(n) candidata.

Ref: Trabajo en prácticas

Algoritmos - Análisis de algoritmos - 8

1.2 Notaciones asintóticas (5) - La notación O

Reglas prácticas para trabajar con la O:

Definición:
f(n) es monótona creciente si n1 ≥ n2 ⇒ f(n1) ≥ f(n2)

Teorema: ∀c > 0, a > 1, f(n) monótona creciente:

(f(n))c = O(af (n))

≡ “Una función exponencial (ej: 2n) crece más rápido que una función
polinómica (ej: n2)”

(

→

nc = O(an)
(logan)c = O(alogan) = O(n)

→ (logn)k = O(n) ∀k constante.

≡ “n crece más rápido que cualquier potencia de logaritmo”
≡ “los logaritmos crecen muy lentamente”

Algoritmos - Análisis de algoritmos - 9

1.2 Notaciones asintóticas (6) - La notación O

Reglas prácticas para trabajar con la O (Cont.):

Suma y multiplicación:
T1(n) = O(f(n)) ∧ T2(n) = O(g(n)) ⇒

(

(1) T1(n) + T2(n) = O(f(n) + g(n)) = max(O(f(n)), O(g(n)))
(2) T1(n) ∗ T2(n) = O(f(n) ∗ g(n))

Aplicación:

(1) Secuencia: 2n2 = O(n2) ∧ 10n = O(n) ⇒ 2n2 + 10n = O(n2)
(2) Bucles

(

Observación: No extender la regla para la resta ni para la división

← relación ≤ en la definición de la O

... suficientes para ordenar la mayoría de las funciones.

Algoritmos - Análisis de algoritmos - 10

1.2 Notaciones asintóticas (7) - Otras notaciones asintóticas

1. O

2. Definición:

T (n) = Ω(f(n)) ssi ∃ constantes c y n0: T (n) ≥ cf(n) ∀n ≥ n0,
T (n), f(n) : Z + → R+

→ f(n): cota inferior de T (n) ≡ trabajo mínimo que realiza un algoritmo
Ejemplo: 3n2 = Ω(n2): es la cota inferior más ajustada;
pero también 3n2 = O(n2)...

3. Definición:

T (n) = Θ(f(n)) ssi ∃ constantes c1, c2 y n0: c1f(n) ≤ T (n) ≤ c2f(n)
∀n ≥ n0, T (n), f(n) : Z + → R+

≡ O ∧ Ω
→ f(n): cota exacta de T (n), del orden exacto
Ejemplo: 5nlog2n − 10 = Θ(nlogn):

(1) demostrar O →< c, n0 >
(2) demostrar Ω →< c0, n0
0 >

(

Algoritmos - Análisis de algoritmos - 11

1.2 Notaciones asintóticas (8) - Otras notaciones asintóticas

4. Definición:

T (n) = o(f(n)) ssi ∀ constante C > 0, ∃n0 > 0: T (n) < Cf(n) ∀n ≥ n0,
T (n), f(n) : Z + → R+

≡ O ∧ ¬Θ ≡ O ∧ ¬Ω
→ f(n): cota estrictamente superior de T (n) ≡ límn→∞ T (n)
Ejemplos:

f (n) = 0

n

n

log2n = o(n)

10 6= o(n)

5. Definición:

T (n) = ω(f(n)) ssi ∀ constante C > 0, ∃n0 > 0: T (n) > Cf(n) ∀n ≥ n0,
T (n), f(n) : Z + → R+

↔ f(n) = o(T (n))
→ f(n): cota estrictamente inferior de T (n)

6. Notación OO [Manber]:

T (n) = OO(f(n)) si es O(f(n)) pero con constantes demasiado grandes
para casos prácticos
Ref: ejemplo 2 (p. 4): B1 = O(n2), B2 = OO(n1,8)

Algoritmos - Análisis de algoritmos - 12

1.2 Notaciones asintóticas (9) - Otras notaciones asintóticas

Reglas prácticas (Cont.):

1. T (n) = a0 + a1n + a2n2 + ... + aknk ⇒ T (n) = Θ(nk)

(polinomio de grado k)

2. Teorema: ∀c > 0, a > 1, f(n) monótona creciente:

(f(n))c = o(af (n))

≡ “Una función exponencial crece más rápido que una función polinómi-
ca” → no llegan a igualarse

Algoritmos - Análisis de algoritmos - 13

1.3 Cálculo de los tiempos de ejecución (1) - Modelo de computación

Calcular O para T (n) ≡ contar número de “pasos” → f(n)? ¿paso?

Modelo de computación:
• ordenador secuencial
• instrucción ↔ paso
• entradas: tipo único (“entero”) → sec(n)
• memoria infinita + “todo está en memoria”

(no hay instrucciones complejas: matrices...)

Alternativas: Un paso es...

1. Operación elemental:

Operación cuyo tiempo de ejecución está acotado superiormente por

una constante que sólo depende de la implementación

2. Operación principal [Manber]:

→= O(1)

Operación representativa del trabajo del algoritmo
Ejemplo: la comparación en un algoritmo de ordenación
El número de operaciones principales que se ejecutan debe ser pro-

porcional al número total de operaciones (verificarlo!)

Algoritmos - Análisis de algoritmos - 14

1.3 Cálculo de los tiempos de ejecución (2) - Modelo de computación

Observación: La hipótesis de la operación principal supone una aproximación
mayor.

En general, se trabaja usando la hipótesis de la operación elemental.

En cualquier caso, se ignora: lenguaje de programación, procesador, sistema
operativo, carga...

⇒ Sólo se considera el algoritmo y el tamaño de la entrada

Debilidades:
• operaciones de coste diferente

(“todo en memoria” ⇒ lectura en disco = asignación)
→ contar separadamente según tipo de instrucción y luego ponderar?
factores ≡ dependiente de la implementación
⇒ costoso y generalmente inútil

• faltas de página ignoradas
• etc.
→ Aproximación

Algoritmos - Análisis de algoritmos - 15

1.3 Cálculo de los tiempos de ejecución (3) - Análisis de casos

Análisis de casos:

Tmejor(n)

Consideramos distintas funciones para T (n):

Tmedio(n) ← representativa, puede más complicada de obtener
Tpeor(n) ← en general, la más utilizada
Tmejor(n) ≤ Tmedio(n) ≤ Tpeor(n)

¿El tiempo de respuesta es crítico?

→ Sistemas de Tiempo Real

Algoritmos - Análisis de algoritmos - 16

Ordenación por Inserción

procedimiento Ordenación por Inserción (var T[1..n])

para i:=2 hasta n hacer

x:=T[i];
j:=i-1;
mientras j>0 y T[j]>x hacer

T[j+1]:=T[j];
j:=j-1

fin mientras;
T[j+1]:=x

fin para

fin procedimiento

3

1

1

1

1

1

1

1

1

1

1

3

3

1

1

1

1

1

1

1

4

4

4

3

2

2

2

2

2

2

1

1

1

4

3

3

3

3

3

3

2

2

2

2

4

4

4

4

4

3

9

9

9

9

9

9

5

5

5

4

5

5

5

5

5

5

9

6

5

5

6

6

6

6

6

6

6

9

6

5

5

5

5

5

5

5

5

5

9

6

3

3

3

3

3

3

3

3

3

9

Algoritmos - Análisis de algoritmos - 17

Ordenación por Selección

procedimiento Ordenación por Selección (var T[1..n])

para i:=1 hasta n-1 hacer

minj:=i;
minx:=T[i];
para j:=i+1 hasta n hacer
si T[j]<minx entonces

minj:=j;
minx:=T[j]

fin si

fin para;
T[minj]:=T[i];
T[i]:=minx

fin para

fin pro