peo*_*oro 13 language-agnostic algorithm complexity-theory programming-languages functional-programming
我知道大多数编程语言都是图灵完备的,但我想知道是否可以使用任何编程语言(特别是任何编程范例)使用相同复杂度的算法来解决问题.
通过一个例子让我的答案更明确:是否有任何问题可以通过复杂的命令式算法解决x(比如说O(n)),但是不能通过具有相同复杂度的功能算法来解决(反之亦然)？
编辑: 算法本身可能不同.问题是解决问题的复杂性 - 使用语言中的任何可用方法.
Eri*_*sen 10
通常,不是,并非所有算法都可以在所有语言中以相同的复杂度实现.例如,使用假设的语言不允许O(1)访问数组,这可以通过简单的证明.但是,没有任何算法(据我所知)无法用功能语言中的最佳复杂顺序实现.算法的伪代码的复杂性分析对哪些操作是合法的以及哪些操作是O(1)做出了某些假设.如果你打破其中一个假设,即使语言是图灵完成,你也可以改变算法实现的复杂性.图灵完整性无法保证任何操作的复杂性.