恒定时间Haskell列表(时间复杂度？Haskell数据类型？) - 与家庭作业相关

Question

我目前正在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的错误.无论如何转换那个？

Answer 1

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

例如,如果您有未分类的名片,搜索特定名片将需要与卡数成比例的步骤.如果你的堆积增加一倍,你需要检查的平均卡数也会增加一倍.

另一方面,如果你预先对卡片进行了分类,你可以玩"高 - 低"游戏,每次看卡片时都会减少一半的尺寸.现在,在寻找特定卡时,加倍堆的大小只需要一个额外的步骤.

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

您通常可以通过使用不同输入在纸上遍历算法来获得想法,但是有更精确的方法.以下是使用标准列表实现的追加函数的示例[]:

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

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