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

根据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