Mat*_*eon 13 algorithm performance haskell functional-programming
prefixes ls = zipWith take [1 .. length ls] (repeat ls)
有什么方法比这更好吗？直觉上,在我看来,在纯函数式语言中无法获得低于O(n²)的算法,因为反向或追加必须应用n次.但我不知道如何证明这一点.
luq*_*qui 19
我想你是对的.由于所有尾部都不同,因此不能共享列表的主干.因此,如果完全评估,前缀列表将采用完整的Θ(n 2)空间,该空间必须花费Ω(n 2)时间来生成.
请注意,您编写的函数(更常见的版本)Data.List可用作inits.
虽然你可以做一个简洁的优化.这个等式成立:
map (foldl f z) . inits = scanl f z
并scanl以线性时间运行.因此,如果您可以将要对每个前缀做的事情标记为左侧折叠,那么您可以避免构建前缀列表的二次复杂性.
| 归档时间： |
|
| 查看次数： |
938 次 |
| 最近记录： |