1

我目前正在 Haskell 上 CS 课程，但在理解某些材料时遇到了一些严重的问题。

对于我的一项任务，我得到了 2 种数据类型，并要求我编写一个具有恒定时间追加的追加函数。

我得到：

data NNList a = Sing a | Append ( NNList a) ( NNList a) deriving (Eq)
data CList a = Nil | NotNil ( NNList a) deriving (Eq)

我被要求写一个函数：

CListAppend :: CList a -> CList a -> CList a

我不确定我在 CS 教育中错过了什么，但我经常发现自己对时间和空间复杂性感到困惑，我怎么知道函数是否是constant time? 任何人都可以向我提供有关如何处理这个问题的一些想法吗？

我的尝试：

CListAppend :: CList a -> CList a -> CList a
CListAppend Nil rl = rl
CListAppend ll Nil = ll
CListAppend ll rl = NotNil $ Append ll rl

这报告和返回 NNList 而不是 CList 的错误。反正有转换吗？

4

2 回答 2

6

时间复杂度是一种描述相对于输入大小计算答案需要多少步的方法。什么构成一个步骤以及如何计算大小取决于问题。

例如，如果您有一堆未分类的名片，则搜索特定的名片将需要与名片数量成正比的多个步骤。如果您将牌堆的大小翻倍，则您必须检查的平均牌数也将翻倍。

另一方面，如果你预先对牌进行分类，你可以玩“高低”游戏，每次看牌时将牌堆的大小减半。现在，在寻找特定卡片时，将牌堆的大小加倍只需要一个额外的步骤。

这些分别是线性和对数时间复杂度的例子。在您的情况下，您需要恒定的时间复杂度。这意味着无论两个列表有多大，附加它们都需要相同数量的步骤。

您通常可以通过使用不同输入在纸上浏览算法来获得一个想法，但还有更精确的方法。下面是一个使用标准列表实现的附加函数示例：[]

append []     bs = bs
append (a:as) bs = a : append as bs

我们将递归调用append算作一个步骤；或者，我们可以计算 的调用次数(:)。当第一个参数是一个空列表时，[]没有递归调用。当列表包含单个元素时[1]，我们评估1 : append [] bs，所以我们有一个递归调用。现在将输入大小加倍[1,2]并计算递归调用。然后用 等再次加倍[1,2,3,4]。然后您可以粗略估计输入大小的步数是否为常数、线性、对数、指数等。

于 2013-03-26T02:41:16.670 回答
0

最后一个定义是错误的。If llis NotNil xand rlisNotNil y那么你的定义应该是

CListAppend (NotNil x) (NotNil y) = NotNil ( Append x y )

但是，您将 Append 应用于 type 的值CList a。

此解决方案也是恒定时间。Append 构造函数不进行任何处理。模式匹配也在恒定时间内发生。

于 2013-03-27T02:04:32.370 回答