有谁知道纯功能编程而不是强制性编程(即产生副作用)时可能发生的最坏的渐近减慢？
从itowlson的评论中澄清:是否存在最知名的非破坏性算法在渐近性上比最知名的破坏性算法差的问题？
最佳答案
根据Pippenger [1996]的说法，在将纯函数式Lisp系统(具有严格的评估语义，而不是惰性的)与可以变异数据的Lisp系统进行比较时，可以将针对以O(n)运行的不纯Lisp编写的算法转换为一种算法。在以O(n log n)时间运行的纯Lisp中(基于Ben-Amram and Galil [1992]关于仅使用指针模拟随机存取存储器的工作)。皮蓬格(Pippenger)还确定了某些算法，您可以做到最好。在不纯系统中存在O(n)的问题，在纯系统中存在Ω(n log n)的问题。
关于本文有一些警告。最重要的是，它不解决惰性函数语言，例如Haskell。 Bird, Jones and De Moor [1997]证明了由Pippenger构造的问题可以在O(n)时间内用一种惰性函数语言解决，但是它们无法确定(据我所知，没有人知道)一种惰性函数语言是否可以解决所有问题与带有变异的语言在相同的渐近运行时间中出现问题。
由皮蓬格(Pippenger)构造的问题需要专门构造Ω(n log n)才能获得此结果，并且不一定代表实际的实际问题。对这个问题有一些限制，这是出乎意料的，但是对于证明工作是必不可少的。特别地，该问题要求结果是在线计算的，而无法访问将来的输入，并且该输入由来自无限可能原子集合的一系列原子组成，而不是固定大小的集合。并且本文仅针对线性运行时间的不纯算法建立(下界)结果。对于需要更长运行时间的问题，可能会在运行时间较长的算法所需的额外操作过程中，“吸收”线性问题中出现的额外O(log n)因子。 Ben-Amram [1996]简要探讨了这些澄清和开放性问题。
实际上，可以用纯功能语言以与具有可变数据结构的语言相同的效率来实现许多算法。有关有效用于实现纯功能数据结构的技术的良好引用，请参见Chris Okasaki's "Purely Functional Data Structures" [Okasaki 1998](这是他的论文[Okasaki 1996]的扩展版本)。
任何需要在纯功能数据结构上实现算法的人都应该阅读Okasaki。通过使用平衡的二叉树来模拟可变内存，您每次操作总是最糟糕的是O(log n)速度变慢，但是在许多情况下，您可以做得更好，而且Okasaki描述了许多有用的技术，从摊销技术到实际应用，逐步进行摊销的时间。纯功能数据结构可能很难使用和分析，但是它们提供了很多好处，例如引用透明性，有助于编译器优化，并行和分布式计算以及版本控制，撤消和回滚等功能的实现。
还要注意，所有这些仅讨论渐近运行时间。许多实现纯功能数据结构的技术会给您一定程度的恒定因子减慢，这是因为它们需要额外的簿记工作以及所涉及语言的实现细节。纯功能数据结构的好处可能胜过这些恒定因素的放缓，因此，通常需要根据相关问题进行权衡。
引用文献