functional-programming - 每个命令式算法在相同的空间和时间复杂度类中是否有一个纯函数等价物？

Question

根据我个人的经验，我想，答案是否定的。以可变数组为例。似乎，通过使用具有随机访问的可变数据结构（即数组）可以最有效地解决某些问题。您可以使用不同的数据结构，例如字典（F# 中的映射），它与函数式方法兼容，但您将无法进行随机访问，并且您的算法效率会因 log n 系数而变差。在一些相当罕见的情况下，使用别名可能不仅方便而且更有效，以便能够以不同的方式访问相同的数据结构。但是混叠也与函数方法的不变性不兼容。

像这样的例子表明，纯函数式方法不可能在所有情况下都像命令式方法那样有效。我当然知道，函数式语言是图灵完备的，但我不记得证明的足够好来判断它是否也告诉我们一些关于时间和空间复杂性的信息。那么从理论的角度来看，我们对此有什么了解呢？我的假设对吗？

标签： functional-programmingf#time-complexityspace-complexity

Answer 1

皮蓬格证明了

1. 与以n步操作的纯程序相比，不纯程序最多存在 log( n ) 乘法开销（在 Big-O 意义上）。
2. 确实存在需要 log( n ) 因子的某些问题。

但是，在一些有趣的问题中，log( n ) 因子不是必需的，并且请记住，常数因子在现实世界的用例中也可能很重要。