Haskell Hero

Haskell Hero es un manual interactivo del lenguaje Haskell para principiantes.

Complejidad temporal

¿Por qué hablamos de la complejidad temporal?

Ejemplo

Determinad que de estas funciones calcula más rápido la elevación del parámetro a una potencia de exponente natural.

eleva1 _ 0  =  1
eleva1 x n  =  x * eleva1 x (n-1)

eleva2 _ 0  =  1
eleva2 x n  =  if even n then r else x * r
               where r = eleva2 (x * x) (n ‘div‘ 2)

Evaluemos por ejemplo las expresiones eleva1 5 1 y eleva2 5 1.

eleva1 5 1

~>  5 * eleva1 5 (1-1)
~>  5 * eleva1 5 0
~>  5 * 1
~>  5

eleva2 5 1

~>  if even 1 then r else 5 * r
    where r = eleva2 (5 * 5) (1 ‘div‘ 2)
~>  if False  then r else 5 * r
    where r = eleva2 (5 * 5) (1 ‘div‘ 2)
~>  5 * eleva2 (5 * 5) (1 ‘div‘ 2)
~>  5 * eleva2 (5 * 5) 0
~>  5 * 1
~>  5

La elevación de cinco a uno usando la función eleva1 se realizó en 4 pasos. La misma elevación usando la función eleva2 se realizó en 6 pasos. Podríamos entonces decir que la complejidad temporal de la función eleva2 es mayor que la complejidad temporal de la función eleva1. Sin embargo, si realizamos la elevación de cinco a diez, el cálculo será un poco diferente:

eleva1 5 10

~>2   5 * eleva1 5 9
~>2   5 * 5 * eleva1 5 8
~>2   5 * 5 * 5 * eleva1 5 7
~>14  5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * eleva1 5 0
~>    5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 1
~>10  9765625

31 pasos en total.

umocni2 5 10

~>3   eleva2 (5 * 5) (10 ‘div‘ 2)
~>    eleva2 (5 * 5) 5
~>3   5 * 5 * eleva2 (5 * 5 * 5 * 5) (5 ‘div‘ 2)
~>    5 * 5 * eleva2 (5 * 5 * 5 * 5) 2
~>3   5 * 5 * eleva2 (5 * 5 * 5 * 5 * 5 * 5 * 5 * 5) (2 ‘div‘ 2)
~>    5 * 5 * eleva2 (5 * 5 * 5 * 5 * 5 * 5 * 5 * 5) 1
~>3   5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 
        eleva2 (5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 *
                 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5) (1 ‘div‘ 2)
~>    5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 
        eleva2 (5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 *
                 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5) 0
~>4   5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 1
~>10  9765625

30 pasos en total. Si usáramos un exponente aún más grande, veríamos que cuanto más grande el exponente, tanto más efectiva es la función eleva2.

La complejidad temporal estudia la complejidad de cómputo dependiente del tamaño de la entrada. Ahora vamos a mencionar conceptos básicos de esta problemática.

La complejidad constante

Funciones cuyos cómputos tienen siempre un número de pasos constante, son de complejidad constante.

Un ejemplo puede ser la función head aplicada a listas de varias longitudes.

head [1]      ~>  1
head [1,2,3]  ~>  1
head [1,2,3,4,5,6,7,8,9,10]  ~>  1

Sin mirar a la longitud de la lista tomada como parámetro la evaluación de la función head tiene siempre un número de pasos constante. En este caso es solo un paso.

Complejidad lineal

Funciones cuyo tiempo de ejecución sube de manera lineal con parámetros más grandes, son de complejidad lineal.

Por ejemplo la función map (+1) es de complejidad lineal respecto al número de elementos de la lista tomada como parámetro.

map (+1) [1]

~> 1+1 : map (+1) []
~> 1+1 : []
~>  2  : []

3 pasos en total cuando aplicada a una lista de un elemento.

map (+1) [1,2]

~> 1+1 : map (+1) [2]
~> 1+1 : 2+1 : map (+1) []
~> 1+1 : 2+1 : []
~>  2  : 2+1 : []
~>  2  :  3  : []

5 pasos en total aplicada a una lista de dos elementos.

map (+1) [1,2,3]

~> 1+1 : map (+1) [2,3]
~> 1+1 : 2+1 : map (+1) [3]
~> 1+1 : 2+1 : 3+1 : map (+1) []
~> 1+1 : 2+1 : 3+1 : []
~>  2  : 2+1 : 3+1 : []
~>  2  :  3  : 3+1 : []
~>  2  :  3  :  4  : []

7 pasos en total aplicada a una lista de tres elementos.

En general podemos decir que con cada otro elemento en una lista el tiempo de ejecución crece en un número de pasos constante, en este caso en dos. Esta función es de complejidad lineal.

Complejidad cuadrática

Tengamos la función estaDosVeces :: Eq a => [a] -> Bool en la que la expresión estaDosVeces s se evalúa a True si hay dos mismos elementos en la lista s y a False si todos los elementos son diferentes.

En vez de la definición exacta solo digamos como tal función va a funcionar.

comprueba si el primer elemento de s no aparece en otro lugar en la lista s
si encuentras tal lugar, evalúase a True
si no aparece otra vez, llama de manera recursiva la función estaDosVeces a la lista s sin el primer elemento

Supongamos que la comparación de dos elementos se hace dentro de un número de pasos constante. Durante la comprobación de cada elemento de la lista hay que siempre examinar todos los otros elementos de la lista. Es decir, se reliza n pasos n veces, donde n es el número de elementos de la lista s. Esto nos indica la complejidad n*n, es decir, n^2. Vamos a decir que funciones cuya evaluación tiene n^2 pasos, son de complejidad cuadrática.

Luego tenemos funciones cuya evaluación tiene n^3 pasos. Estas son de complejidad cúbica. En general, las funciones de complejidad n^a, donde a es una constante, las llamamos funciones de complejidad polinómica.

Complejidad logarítmica

Hay también funciones que se evalúan dentro de más pasos de las funciones constantes pero también dentro de menos pasos que funciones lineales. Estas son funciones de complejidad logarítmica.

Un ejemplo de tal función puede ser por ejemplo la función siguiente:

calcula x  =  if x < 1 then 0
                       else calcula (x `div` 2)

Como podéis ver, la función no calcula nada útil. Siempre devuelve cero. Sin embargo, la evaluación siempre tendrá un diferente número de pasos dependiente del parámetro. Por ejemplo:

   calcula 5
~>  calcula 2
~>  calcula 1
~>  calcula 0
~>  0

    calcula 10
~>  calcula 5
~>  calcula 2
~>  calcula 1
~>  calcula 0
~>  0

    calcula 1000
~>  calcula 500
~>  calcula 250
~>  calcula 125
~>  calcula 62
~>  calcula 31
~>  calcula 15
~>  calcula 7
~>  calcula 3
~>  calcula 1
~>  calcula 0
~>  0

Como podemos ver, la evaluación de la expresión calcula 5 tiene 4 pasos, la evaluación de calcula 10 tiene 5 pasos y la evaluación de calcula 1000 tiene 11 pasos. Podemos decir que la función calcula es de complejidad logarítmica.

<= Evaluación II lección anterior