初始化函数的时间复杂度

Question

我正在尝试删除Haskell中列表的最后一个元素，并已找到有关该init功能的信息。由于我要使用的函数必须是O（n），所以我想知道它的时间复杂度init是多少。

Answer 1

init :: [a] -> [a]被实现为[src]：

init [] =  errorEmptyList "init"
init (x:xs) =  init' x xs
  where init' _ [] = []
        init' y (z:zs) = y : init' z zs

为了生成一个列表，它会在源列表上进行迭代，每次查看前一个元素并发出前一个元素时（假定尾部不是空列表）。

因此，这意味着对于n个元素的列表，将花费O（n）时间来计算该init列表的。

但是在Haskell函数中，调用是惰性的。例如，如果您只对采用第一个k元素感兴趣，它将在O（ min（n，k））中运行。