因为Haskell中的列表查找,它是O(n^2)吗?
是的。
如果是,那么有没有办法使其像查找操作是O(1)的语言一样变成O(n)?
最简单的方法是使用惰性数组,它们具有O(1)的随机访问。这意味着,您必须指定一个数组大小,因此您不再具有无限序列,但在其他语言中也存在相同的限制。例如,您可以使用 Data.Vector
来实现:
import Data.Vector
fibsUpto100 :: Vector Integer
fibsUpto100 = generate 100 fib
where fib 0 = 0
fib 1 = 1
fib n = fibsUpto100 ! (n-1) + fibsUpto100 ! (n-2)
由于惰性,只有在对向量的元素进行评估时才会计算任何内容,在此之前未被评估的先前向量元素也将被评估。一旦评估完成,每个值都存储在向量中,因此不会重复评估。
当然,拥有无限数字列表会更好。实现这一点的一种方法是将计算第n个斐波那契数的标准O(n)方式(使用while循环跟踪当前和上一个元素)转换为递归Haskell函数,然后调整该函数以将每个元素存储在列表中。
while循环的基本转换如下:
fib 0 = 0
fib n = fibHelper n 0 1
where
fibHelper 0 _ current = current
fibHelper n previous current =
fibHelper (n-1) current (current + previous)
如果我们将这个调整为保持列表,那么得到:
fibs = 0 : genFibs 0 1
where
genFibs previous current =
current : genFibs current (current + previous)
另一种更简洁的方法是使用列表自身的尾部来定义列表。也就是说,我们希望列表的每个元素都是前一个元素加上它前面的元素,我们通过将列表及其尾部相加并将结果反馈回列表来实现这一点。这导致以下定义:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
这里的0和1分别是第一和第二个元素,其余元素在
zipWith (+) fibs (tail fibs)
生成的列表中。该列表的第一个元素(即整个列表的第三个元素)将是
fibs
的第一个元素加上
tail fibs
的第一个元素,因此
0 + 1 = 1
,下一个元素将是
1 + 1 = 2
等等。因此,这个定义确实产生了斐波那契数列。
¹ 尽管对于不太习惯在头脑中打递归结构的人来说,这可能会更加难以理解。