Análisis de la complejidad de los algoritmos

1 La notación de Landau

1.1 Definición de O(g)

limsup   |f(x)/g(x)| < ∞
x → ∞

1.2 Propiedades

2 Órdenes de complejidad

2.1 Principales órdenes de complejidad

Orden Nombre
O(1) constante
O(log n) logarítmica
O(n) lineal
O(n log n) casi lineal
O(n²) cuadrática
O(n³) cúbica
O(a^n) exponencial

2.2 Tasas de crecimiento

2.3 Jerarquía de complejidad

2.4 Efectos de duplicaciones

T(n) n = 100 n = 200
log(n) 1 h. 1.15 h.
n 1 h. 2 h.
nlog(n) 1 h. 2.30 h.
1 h. 4 h.
1 h. 8 h.
2ⁿ 1 h. 1.27*10³⁰ h.
T(n) t = 1h t = 2h
log(n) n = 100 n = 10000
n n = 100 n = 200
nlog(n) n = 100 n = 178
n = 100 n = 141
n = 100 n = 126
2ⁿ n = 100 n = 101

3 Ejemplo de función con complejidad lineal O(n)

3.1 Especificación de la función suma

suma 5  ==  15

3.2 Definición recursiva de la función suma

suma :: Integer -> Integer
suma 0 = 0
suma n = n + suma (n-1) 

3.3 Estadísticas de la función suma

n segs
1000 0.02
2000 0.03
3000 0.04
4000 0.04
5000 0.05
6000 0.06
7000 0.07
8000 0.08
tiempo(suma n) ≈ n * 0.00001

3.4 Ecuaciones de coste de la función suma

T(1)   = 1
T(n+1) = 1 + T(n)

3.5 Demostración de que suma ∈ O(n) (es decir, es de coste lineal)

T(1)   = 1       [por definición de T]
T(n+1) = 1+T(n)  [por definición de T]
       = 1+n     [por hipótesis de inducción]
       = n+1     [por álgebra]

4 Ejemplo de función con complejidad constante O(1)

4.1 Definición de la función suma mediante la fórmula

suma2 :: Integer -> Integer
suma2 n = n*(n+1) `div` 2

4.2 Estadísticas de la función suma2

n segs.
1000 0.01
2000 0.01
3000 0.01
4000 0.01
5000 0.01
6000 0.01
7000 0.01
8000 0.01
tiempo(suma n) ≈ 0.01

4.3 Ecuaciones de coste de la función suma2

T(1) = 1

4.4 Demostración de que suma2 ∈ O(1) (es decir, es de coste constante).

5 Ejemplo de función con complejidad cuadrática O(n²)

5.1 Especificación de la función sumaDeSumas

sumaDeSumas n = (suma 0) + (suma 1) + ... + (suma n)

5.2 Definición recursiva de la función sumaDeSumas

sumaDeSumas :: Integer -> Integer
sumaDeSumas 0 = 0
sumaDeSumas n = suma n + sumaDeSumas (n-1)

5.3 Estadísticas de la función sumaDeSumas

n segs
100 0.06
200 0.17
300 0.35
400 0.62
500 0.96
600 1.37

5.4 Gráfica de coste de sumaDeSumas

5.5 Ecuaciones de coste de la función sumaDeSumas

 T(1)   = 1
 T(n+1) = T(suma(n+1))+T(n)
        = n+1+T(n)

5.6 Demostración de que sumaDeSumas ∈ O(n²) (es decir, es de coste cuadrático)

T(1) = 1 ≤ 1²
T(n+1) 
= n+1+T(n)     [por coste de sumaDeSumas.2]
≤ n+1+n²       [por hip. de inducción]
≤ n²+2n+1      [por álgebra]
= (n+1)²       [por álgebra]

6 Ejemplo de función con complejidad exponencial O(2ⁿ)

6.1 Especificación de la función raiz

x(0)   = 1
x(n+1) = (x/x(n) + x(n))/2

Por ejemplo,

ghci> raiz 9 5
3.0
ghci> raiz 16 5
4.0000005
ghci> raiz 16 10
4.0

6.2 Definición recursiva de la función raiz

raiz :: Float -> Int -> Float
raiz x 0 = 1 
raiz x n = (x / (raiz x (n-1)) + (raiz x (n-1))) / 2.0

6.3 Estadísticas de la función raiz

n segs
14 0.14
15 0.27
16 0.53
17 1.04
18 2.03
19 4.08
20 8.10

6.4 Ecuaciones de coste de la función raiz

T(0)   = 1
T(n+1) = 2*T(n)

6.5 Demostración de que raiz ∈ O(2ⁿ) (es decir, es de coste exponencial)

T(0) = 1 = 2^0
T(n+1) 
= 2*T(n)   [por coste de raiz]
= 2*2ⁿ     [por hip. de inducción]
= 2^(n+1)  [por álgebra]

7 Ejemplo de función con complejidad logarítmica O(log n)

7.1 Especificación de la función potencia

x^n = (x*x)^(n/2),   si n es par
x^n = x*(x*x)^(n/2), si n es impar

7.2 Definición recursiva de la función potencia

potencia :: Integer -> Integer -> Integer
potencia x 0 = 1
potencia x n | even n    = potencia (x*x) (div n 2)
             | otherwise = x * potencia (x*x) (div n 2)

7.3 Estadísticas de la función potencia

n segs
1024 0.01
2048 0.02
4096 0.04
8192 0.07
16384 0.14
32768 0.26

7.4 Ecuaciones de coste de la función potencia

T(1) = 1
T(n) = 1 + T(n/2)

7.5 Demostración de que potencia ∈ O(log n) (es decir, es de coste logarítmico)

T(1) = 1 = 1 + log 1
T(n) 
= 1 + T(n/2)           [por coste de potencia]
= 1 + (1 + log(n/2))   [por hipótesis de inducción]
= 1 + (1 + log n - 1)  [por álgebra]
= 1 + log n            [por álgebra]

8 Complejidad de la función inversa

8.1 Especificación de la función inversa

inversa [3,2,5,7] ==  [7,5,2,3]

8.2 Primera definición de inversa: inversa1

inversa1 []     = []
inversa1 (x:xs) = inversa1 xs ++ [x]

8.3 Coste de inversa1

T(0)   = 1
T(n+1) = T(n) + n + 1

8.4 Segunda definición de inversa: inversa2

inversa2 :: [a] -> [a]
inversa2 xs = aux [] xs
    where aux ys []     = ys
          aux ys (x:xs) = aux (x:ys) xs

8.5 Coste de inversa2

T(0)   = 1
T(n+1) = 1 + T(n) 

8.6 Comparación gráfica de costes de inversa1 e inversa2

9 Apéndices

9.1 Algunas recurrencias simples para el cálculo de coste

| Ecuaciones         | Orden      | Ejemplo     |
|--------------------|------------|-------------|
| T(1) = k           | O(1)       | suma2       |
|--------------------|------------|-------------|
| T(1)   = k         | O(n)       | suma        |
| T(n+1) = T(n)+k'   |            |             |
|--------------------|------------|-------------|
| T(1)   = k         | O(n²)      | sumaDeSumas |
| T(n+1) = T(n)+n    |            |             |
|--------------------|------------|-------------|
| T(1)   = k         | O(log(n))  | potencia    |
| T(n)   = T(n/2)+k' |            |             |
|--------------------|------------|-------------|
| T(0)   = k         | O(2ⁿ)      | raiz        |
| T(n+1) = 2T(n)+k'  |            |             |
|--------------------|------------|-------------|
| T(1)   = k         | O(nlog(n)) | ordenación  |
| T(n)   = 2T(n/2)+n |            | por mezcla  |

9.2 Teorema maestro para el cálculo de coste

9.3 Complejidades de los algoritmos habituales

10 Bibliografía



Universidad de Sevilla

José A. Alonso Jiménez
Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e I.A.
Universidad de Sevilla