Haskell列表（时间复杂性？Haskell数据类型？） - 作业相关

我目前正在Haskell中学习CS课程，并且在理解一些材料时遇到了一些严重问题。Haskell列表（时间复杂性？Haskell数据类型？） - 作业相关

对于我的任务之一，我给了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的错误。无论如何要转换吗？

来源

2013-03-26 rlhh

您不希望在您的功能中执行的工作在输入大小方面发生显着变化。在你的情况下，你可能不希望在一个恒定时间的解决方案中使用递归。 – copumpkin 2013-03-26 01:54:29

提示：你必须返回一个'CList'。 “CList”的构造函数是什么？ – hammar 2013-03-26 02:11:38

@hammar，我怎样才能在Haskell中构建一些东西？它肯定不是'CList $ Append ll rl'或类似的东西.. – rlhh 2013-03-26 02:14:56

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

例如，如果您有一堆未排名的名片，搜索特定的名片将需要一些与卡数成正比的步骤。如果你的堆的大小加倍，你必须检查的平均卡数也会增加一倍。另一方面，如果您预先对卡片进行了分类，则可以在每次观看卡片时玩“高低”游戏以减少一半的大小。现在只需加倍一堆一个寻找一个特定的卡。

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

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

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

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

来源

2013-03-26 02:41:16 kputnam

最后一个定义是错误的。如果ll是NotNil x和rl是NotNil y那么你的定义应该是

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

不过，您在CList a类型的值将追加。

此外这种解决方案是恒定的时间。追加构造函数没有处理。模式匹配也会在不断的时间内发生。

来源

2013-03-27 02:04:32

Haskell列表（时间复杂性？Haskell数据类型？） - 作业相关

回答

相关问题