Dav*_*Gao -2 algorithm performance functional-programming imperative-programming asymptotic-complexity
我对IP和FP的性能有疑问.假设我有一个计算第n个Fibonacci数的函数.
在命令式编程中,我可以选择使用迭代方式,递归或动态编程来计算第n个Fibonacci数.当然,与递归渐近相比,迭代方式和动态编程将表现得更好.
在函数式编程中,假设没有涉及的状态,那么我只能以递归的方式进行.
在这种情况下,这并不意味着功能编程在效率方面与渐进式编程相比总是表现得相同或更慢(渐近)？
现实世界的函数式编程如何处理这个问题？
实现Fibonacci数字没有一种递归方式.您可以轻松编写递归函数,在O(n)时间内计算第n个Fibonacci数 - 它的工作方式与迭代版本相同(即它跟踪您计算的最后两个数字),但是使用尾递归而不是命令循环.由于许多函数语言需要实现来执行尾调用优化,因此与迭代版本相比,甚至不会有恒定的开销.
当然,甚至有一些方法可以计算次线性时间内的第n个斐波那契数(使用闭合形式或矩阵乘法),它在功能语言中与命令式语言一样有效.
关于动态编程:完全可以在函数式语言中进行动态编程.由于动态编程算法在第一次写入时不会改变数组的字段,因此这里的函数编程确实没有矛盾.您所需要的只是在构造数组时能够访问数组的已构造部分.Haskell中存在的惰性数组对此很有用.