代码之家 › 专栏 › 技术社区 › Zazaeil

利用单元体把二次时间规划转化为线性时间规划?

time-complexity functional-programming algorithm

0

Zazaeil · 技术社区 · 7 年前

当我读到一篇专门研究延田引理的论文,以及它与Profuncors光学的关系时,我遇到了以下陈述:

…凯莱单倍体定理(这是使用累积参数的诀窍, 通常可以将二次时间程序转换为线性时间程序…

我感兴趣的部分是 the trick ... quadratic-time... into a linear-time one . 它是如何工作的?

另外,我熟悉monoids和它们常用的数学符号,所以如果必要的话,可以随意使用它,或者坚持使用haskell。

1 回复 | 直到 7 年前

1

2

Lutz Lehmann 7 年前

根据H.Bird的原始论文,该声明的主要示例是简单链接列表的列表反转,可以定义为

reverse([a : x]) = append(reverse x, a)

在直接实现中,附加 a 在尾巴的背面 x 要求 n-1 查找要查找结尾的操作,并且操作计数为 reverse x 所以总的努力是 (n-1)+...+2+1=n*(n-1)/2 .

线性实现使用了 append 操作AS append(x,y) 成本与 X ,而长度 y 不扮演任何角色。作为部分操作, 追加 是列表空间上的自同态, append(x) y = append(x,y) . 现在将这些自同态的串联表示为颠倒的列表

reverse([a1,a2,...,an])=append(an) ... append(a2) append(a1) []

从中列表重建是一个线性成本操作。以前的二次“主要”成本在操作堆栈的管理中是“隐藏”的。但是,最终并不需要这样做,因为结果列表的重建可以从提取第一个元素开始。这需要“累积元素”,在同一个伪代码中

reverse(x) = reverse_recursion(x,[])

哪里

reverse_recursion([a : x], y) = reverse_recursion(x, [a : y])

具有

reverse_recursion([], y) = y