algorithm - 不同编程范式的算法复杂度

Question

我知道大多数编程语言都是图灵完备的，但我想知道是否可以使用与任何编程语言(尤其是任何编程范式)具有相同复杂性的算法来解决问题。

用一个例子让我的回答更明确:是否有任何问题可以用复杂度 x 的命令式算法解决(比如 O(n))，但不能通过具有相同复杂度的函数算法解决(反之亦然)？

编辑: 算法本身可能不同。问题是关于解决问题的复杂性——使用语言中可用的任何方法。

Answer 1

一般来说，不，并非所有算法都可以在所有语言中以相同的复杂度顺序实现。这可以很简单地证明，例如，使用一种不允许 O(1) 访问数组的假设语言。但是，没有任何算法(据我所知)不能以函数式语言的最佳复杂度顺序实现。算法伪代码的复杂性分析对哪些操作是合法的以及哪些操作是 O(1) 做出了某些假设。如果您打破其中一个假设，即使语言是图灵完备的，您也可以改变算法实现的复杂性。图灵完备性不保证任何操作的复杂性。