Tengo la siguiente función que tiene una complejidad exponencial:

c :: Integer -> Integer
c n 
   | n <= 4 = n + 10
   | otherwise = c (n-1) + 2 * (c (n-4))

Estoy luchando por hacer que la complejidad de esta función sea lineal.

c x debe terminar incluso si 1000

1
kekukk 12 ene. 2017 a las 09:40
2
 – 
n. 1.8e9-where's-my-share m.
12 ene. 2017 a las 10:33
Puede simplemente tabular los valores para esa función a partir de 0 y reemplazar las llamadas recursivas con búsquedas en esta tabla. Usando una lista simple, esto se convierte en O (n ^ 2). Según lo sugerido por n.m. esto puede evolucionar de una manera que evite las búsquedas de O (n) y logre una complejidad total de O (n).
 – 
Bakuriu
12 ene. 2017 a las 10:51
1
 – 
Zeta
12 ene. 2017 a las 13:21

1 respuesta

La mejor respuesta

Hay al menos dos formas de resolver este problema linealmente en el tiempo.

Usando memoria intermedia

c1 :: Integer -> Integer
c1 n 
  | n <= 4 = n + 10
  | otherwise = go n (map c1 [4,3,2,1])
  where
    go 4 (a:_) = a 
    go n [a,b,c,d] = go (n-1) [a + 2*d, a, b, c]

Aquí usamos cuatro registros intermedios y los desplazamos mientras go atravesamos el ciclo. Podríamos usar tupla (a, b, c, d) en lugar de una lista, pero es más útil comenzar con el mapeo aquí.

Esta solución es constante en el espacio y lineal en el tiempo.

Memoización (generación de codatos)

c2 :: Integer -> Integer
c2 n
  | n <= 4 = n + 10
  | otherwise = results !! fromInteger (n - 1)
  where
    results = [11..14] ++ zipWith f (drop 3 results) results 
    f a b = a + 2*b

Aquí utilizamos la pereza de Haskell (estrategia de evaluación normal + memorización). La lista infinita results genera valores uno por uno bajo demanda. Es usado como datos por la función c2 que solo solicita al generador para n - ésimo número, y en autodefinición. Al mismo tiempo, estos datos no existen hasta que se necesitan. Este tipo de datos se llama codata y es bastante común en Haskell.

Esta solución es lineal en el espacio y el tiempo.

Ambas soluciones manejan números negativos y números positivos grandes.

5
samsergey 13 ene. 2017 a las 08:08
Otro enfoque es expresar la recurrencia en términos de multiplicación de matrices. Es decir, dado un vector de columna de cuatro elementos sucesivos de la secuencia, puede multiplicarlos a la izquierda por una matriz fija para obtener los siguientes cuatro elementos de la secuencia. m * m * m * ... * v. Pero esto es solo m ^ k * v, y usando la exponenciación al elevar al cuadrado (stimesMonoid), este cálculo es mucho más eficiente, en la práctica, que c1.
 – 
dfeuer
13 ene. 2017 a las 00:55
1
@dfeuer, De hecho, ese es un excelente enfoque matemático para fórmulas recurrentes, tanto elegantes como prácticas. En los casos generales no numéricos (o no lineales), los ciclos iterativos o la memorización siguen siendo útiles.
 – 
samsergey
13 ene. 2017 a las 08:04