gpt4 book ai didi

list - 为什么 Haskell 列表的 `++` 是递归实现的并且花费 O(n) 时间?

转载 作者:行者123 更新时间:2023-12-03 13:52:39 27 4
gpt4 key购买 nike

据我了解,Haskell 中的列表类似于 C 语言中的链接列表。

所以对于下面的表达式:

a = [1,2,3]
b = [4,5,6]
a ++ b

Haskell 以递归方式实现这一点,如下所示:
(++) (x:xs) ys = x:xs ++ ys

时间复杂度为 O(n) ..

但是,我想知道为什么我不能实现 ++更有效率。

最有效的方法可能是这样的:
  • 复制(fork)a ,我们称之为a' ,在 O(1) 中可能有一些技巧可以做到这一点时间
  • 制作 a' 的最后一个元素指向 b 的第一个元素.这可以在 O(1) 中轻松完成时间..

  • 有人对此有想法吗?谢谢!

    最佳答案

    这几乎就是递归解决方案所做的。是a的复制品这需要 O(n) (其中 na 的长度。b 的长度不会影响复杂性)。

    复制 n 的列表确实没有“技巧”。 O(1) 时间内的元素。

    关于list - 为什么 Haskell 列表的 `++` 是递归实现的并且花费 O(n) 时间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30692645/

    27 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com