时间戳

首页 > 解决方案 > haskell 函数的时间复杂度

list - haskell 函数的时间复杂度

问题描述

有没有一种简单的方法来控制haskell中函数的时间复杂度？

我已经构建了一个反转任何类型列表的函数，目标是使其具有线性时间复杂度，我试图这样解决：

rev :: [a] -> [a]
rev(x:[]) = [x]
rev(x:xs) = (rev xs) ++ [x]

我的意图是让它成为线性的，O(n)，但我不确定它是否真的是这样，因此我想使用某种类型的工具来分析代码/函数以表明它实际上是线性的。

因此，我想知道：

这个函数是线性的吗？我可以用任何分析工具展示它吗？

标签： listfunctionperformancehaskelltime-complexity

解决方案

（...）它是线性的，O（n），但我不确定它是否真的是，因此我想使用某种类型的工具来分析代码/函数以表明它实际上是线性的。

该函数不是线性的。append 函数(++) :: [a] -> [a] -> [a]是线性的。由于我们对列表中的每个元素都执行此操作，因此最终的时间复杂度为O(n 2 ) 。

为了使它成为线性函数，我们可以做的是使用累加器：我们每次使用的额外参数将以更新形式传递：

myrev :: [a] -> [a]
myrev = (`go` [])
  where go (x:xs) ys = go xs (x:ys)
        go [] ys = ys

因此，我们从一个空列表开始累加器。对于原始列表中的每个元素，x我们将其从第一个列表中弹出，并将其推送到第二个列表。当第一个列表用尽时，则ys包含反向列表。

推荐阅读