这个函数的计算复杂度是O(2 ^ n)还是O(n)

Question

我想创建一个函数,创建一个无限列表,它将两个数字和一个运算符作为输入,因此它可以生成算术和几何序列.

infiniteList:: (Floating a)=>a->(a->a->a)->a->[a]
infiniteList start operation changeby = 
  start:[(operation x changeby)| x<-(infiniteList start operation changeby)]

代码编译并正常工作:infiniteList 1 (*) 2从1开始生成一个列表,后续数字是其前身的两倍.

现在我无法确定"计算列表的第n个元素"的计算复杂度.从技术上讲,它正在进行一项操作来确定列表中的每个元素.但是,如果您在(2 ^ k +1)项之后,我将不得不等待计算机首先完成计算2 ^(k + 1)个元素.

我希望我能正确地解释这一点,所以基本上我认为程序以2 ^ k批次生成元素,其中k是一个整数,所以你可能会等待(2 ^(k + 1)-2 ^ k)时间计算(2 ^ k +1)整数.那么"计算列表的第n个元素"的计算复杂度是多少？

Answer 1

关键工具是以下规则:

在分析绑定的性能(而不是整体)时,您可以在分析其右侧时假设绑定本身已经完全评估.

您正在定义infiniteList,因此您可以假设在RHS中,infiniteList已完全评估绑定.遗憾的是,这infiniteList只是一个功能,因为它只是一个功能,而且完全评估它只是给你功能!

但是你可以使用这个推理工具找出一个修复:你必须绑定正确的东西.

infiniteList :: a -> (a -> a -> a) -> a -> [a]
infiniteList start operation changeby =
  let result =
    start : [operation x changeby | x <- result]
  in result

现在你有了一个有用的绑定,result你可以假设它是完全评估的!在RHS中,你现在基本上已经

start : map (\x -> operation x changeby) result

这很清楚O(n).

确实有第一个定义,

> infiniteList 1 (*) 2 !! 10000

花费的时间比我想要的要长,但是使用修改后的定义,即使在GHCi中也只需要0.04秒.