文章/答案/技术大牛

发布

社区首页 >问答首页 >函数复杂度从指数到线性

问函数复杂度从指数到线性
EN

Stack Overflow用户

提问于 2017-01-12 06:40:19

回答 1查看 163关注 0票数 1

我有以下函数，它具有指数复杂性：

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

我很难把这个函数的复杂性变成线性。

即使1000 c x仍应终止

haskell

time-complexity

回答 1

Stack Overflow用户

回答已采纳

发布于 2017-01-12 10:49:07

线性地解决这个问题至少有两种方法。

使用中间存储器

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)而不是列表，但是从这里开始映射比较方便。

这个解在空间上是常数的，在时间上是线性的。

回溯(共数据生成)

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 (正常的评估策略+回忆录)。无限列表results按需一个一个地生成值.它被c2函数用作数据，它只要求生成n-th号，并在自定义中使用。同时，这些数据在需要之前是不存在的。这类数据称为codata，在Haskell中相当常见。

这个解在空间和时间上是线性的。

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

票数 5

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/41606660

复制

相似问题

问函数复杂度从指数到线性
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问函数复杂度从指数到线性EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问函数复杂度从指数到线性
EN