函数复杂度从指数到线性

Question

我有以下具有指数复杂性的函数:

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

我正在努力使这个功能的复杂性变为线性.

c x 即使1000 <x <100000,也要终止

Answer 1

至少有两种方法可以及时线性地解决这个问题.

使用中间记忆

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]

在这里,我们使用四个中间寄存器,并在go整个循环中移位它们.我们可以使用元组(a, b, c, d)而不是列表,但是从这里开始映射更方便.

该解决方案在空间上是恒定的并且是时间线性的.

记忆(codata generation)

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

这里我们使用Haskell的懒惰(正常评估策略+ memoization).无限列表results 根据需要逐个生成值.它被用作c2函数的数据,它只是请求生成器为n-th number和自定义.同时,在需要之前,该数据不存在.这种数据称为codata,在Haskell中相当常见.

该解决方案在空间和时间上是线性的.

两种解决方案都处理负数和大正数.