0

例如，一个函数通过 consing 创建一个列表：

fun example1 _ _ [] = []
  | example1 f g (x::xs) =
    if f x
    then (g x)::(example1 f g xs)
    else x::(example1 f g xs)

一个通过尾调用累加器创建一个列表：

fun example2 f g xs =
    let fun loop acc [] = acc
          | loop acc (x::xs') =
            if f x
            then loop (acc@[(g x)]) xs'
            else loop (acc@[x]) xs'
    in
        loop [] xs
    end

在给定相同参数的情况下生成相同的列表。

哪个函数的运行时间更好？

追加操作是否会@遍历到列表的末尾以追加并最终与 consing 解决方案具有相同的运行时间，但使用更少的空间和稍微复杂的代码？

consing 或 append 是否会创建一个全新的元素（对象的深层副本），即使原始元素没有更改或者它只是重用现有元素？

这个问题为这个问题提供了一个更具体的例子

4

1 回答 1

3

x :: xs创建一个新的列表单元，其头部为x，尾部为xs。它不会创建副本xs- 既不深也不浅。所以这是一个 O(1) 操作。

xs @ [x]创建一个浅表副本，xs其中先前最后一个节点的尾部是 now [x]。这是一个O(n)操作。

所以你的函数的时间复杂度是，你的函数example1的时间复杂度是。这两个功能都消耗辅助空间。因为它的堆栈使用以及因为在堆上创建不属于结果列表的列表。O(n)example2O(n^2)O(n)example1example2@

如果在到达列表末尾时更改example2为使用::而不是@然后在结果上使用，它的运行时间将为，但它仍然会比在末尾反转列表的额外成本要慢一些。然而，这可能是一个可以接受的价格，以便能够在没有堆栈溢出的情况下处理大型列表。List.revO(n)example1

于 2013-03-24T13:33:46.760 回答