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

Question

我知道大部分编程语言都是图灵完备的，但我想知道是否可以用任何编程语言（尤其是任何编程范式）的算法以相同复杂度解决问题。

为了更明确说明我的问题，举个例子：是否存在一些问题，可以使用时间复杂度为x（例如O(n)）的命令式算法解决，但无法通过具有相同复杂度的函数式算法解决（或反之亦然）？

编辑：算法本身可以不同，问题在于解决问题的复杂度——使用语言中可用的任何方法。

- peoro

---

@leppie：嗯，好吧，我对此并不确定，这就是为什么我在问的原因...例如，命令式算法通常无法使用纯函数式语言实现。 - peoro

@leppie 我喜欢编写可以在Prolog和C中运行的代码。这样做会带来最有趣的难题。 - user166390

@peoro 这个问题只是在询问解决问题的复杂度问题，而不是针对特定算法选择所需的方法？例如，是否可以替换算法以保持复杂度？如果确实是这种情况，似乎会有反例。 - user166390

我倾向于认为算法的复杂性是实现的属性，而不是语言本身的属性。例如，想象一下一个Brainfuck实现，它进行某些优化，以便在特定的已知循环以“兼容”的状态进入时，宇宙会“瞬间”更新循环的净结果（比如O(1)查找）。然后，需要随机访问的用户“只需”确保按照规定的方式使用系统，以便触发优化。 - mokus

谁可以投票关闭这个问题？这是一个非常酷和有趣的编程问题...如果需要，我会投票重新打开它。 - SyntaxT3rr0r

Answer 1

一般而言，不是所有的算法都可以在所有语言中以相同的复杂度实现。例如，假设有一种语言禁止对数组进行O(1)的访问，那么这一点就变得微不足道了。然而，在函数式语言中没有任何算法（据我所知）无法以最优复杂度实现。算法伪代码的复杂度分析对哪些操作合法、哪些操作为O(1)做出了某些假设。如果打破其中一个假设，即使该语言是图灵完备的，您也可以改变算法实现的复杂度。图灵完备性不能保证任何操作的复杂度。

- Eric Mickelsen

---

虽然我不确定，但可能会发现，一个纯函数式语言可能无法实现一个空间复杂度为x（而非n）且时间复杂度渐近小于log(x)的算法。 - Eric Mickelsen

大多数函数式语言都没有一种能够表示有序集合（例如数组）并允许以O（1）复杂度更改其内容的数据结构。最好的选择是O（log N）。 - salva

+1 给 Salva 关于纯函数式更新的回答。不过公平地说，由于缓存行为和其他因素，O(log N)“纯”数据结构的实际性能可以与 O(1) 破坏性更新相当。 - comingstorm

Answer 2

算法的运行时间可以通过O(n)等方式进行衡量，就像你所说的那样，算法的实现必须遵循相同的运行时间，否则它们就不能实现该算法。语言或实现本身并不会改变算法，因此也不会改变渐近运行时间。

尽管如此，某些语言和技术可能会使表达算法更加容易，并且由于语言的编译或执行方式而提供恒定的加速（或减速）。

- Andrew White

---

所以任何问题都可以在C语言中解决，也可以在brainfuck、lisp、prolog或C++模板中使用相同复杂度的算法来解决吗？ - peoro

@Andrew：反例：在C语言中，我可以在排序后的数字数组中以log n时间找到给定的数字，但在brainfuck中却不能。 - sepp2k

@Andrew：我的意思是你不能使用任何算法在Brainfuck中完成它。 - sepp2k

随机访问在Brainfuck语言中，与当前单元格的距离为O(n)。由于二分查找算法涉及跳过与n成比例的内存区域，因此无法在log（n）时间内实现。 - Eric Mickelsen

一个 Brainfuck 运行时始终可以优化像 [-] 这样的标准操作。你知道，在一些更古老的 RAM 设计中，RAM 探针可能需要 O(n) 的时间从位 0x0000 移动到 0x000f，在这种情况下它不再是 O(1) 时间了。当然，您可以争辩说它不再是“随机访问”内存，但任何内存都不是真正的随机访问。 - SOFe

Answer 3

我认为一种语言可以有不同的基本操作，其成本为O(1)，例如数学运算（+、-、*、/）、变量/数组访问（a[i]）、函数调用以及您能想到的所有操作。

如果一种语言没有这些O(1)操作之一（例如脑弯曲不具有O(1)数组访问），它就无法像C语言一样以相同的复杂度完成所有任务，但如果一种语言具有更多的O(1)操作（例如具有O(1)数组搜索的语言），它就可以完成比C语言更多的任务。

我认为所有“严肃”的语言都具有相同的基本O(1)操作，因此它们可以以相同的复杂度解决问题。

- Ritardi Giuseppe

Answer 4

我认为你的第一段是错误的。而且我认为你的编辑并没有改变它。

假设您要求实现的观察行为符合算法的时间复杂度，那么...

计算算法复杂度时会做出关于哪些操作是恒定时间的假设。这些假设是你将找到线索的地方。

一些更常见的假设是恒定时间数组访问、函数调用和算术操作等。

如果您无法在常量时间内使用语言提供这些操作，则无法以保留时间复杂度的方式重现算法。

合理的编程语言可以打破这些假设，并且有时必须这样做，比如处理不可变数据结构共享状态、并发等问题。

例如，Clojure使用树来表示向量。这意味着访问时间不是恒定的（我认为它是数组大小的log32，但即使它也可能是恒定的）。

您可以轻松想象一种语言在调用函数时必须在运行时执行复杂的操作。例如，决定指的是哪一个。

曾经有一段时间，浮点数和多字节整数乘除法不幸地不是常数时间（它们是在软件中实现的）。在语言过渡到使用硬件的时期，非常合理的语言实现表现出了非常不同的行为。

我也很确定你可以想出在不可变数据结构世界中表现非常糟糕的算法。我见过一些优化算法，在处理不可变性时，可能会非常困难，甚至是不可能或者有效地这样做，而不破坏时间复杂度。

值得一提的是，存在一些算法假定集合并和交是常数时间...祝你好运以常数时间实现这些算法。还有一些算法使用“预言机”，可以在常数时间内回答问题...祝你也好运。

- hutch

---

任何假设实数的算法都是潜在的乐趣来源。这些算法假设除法等操作具有恒定时间，同时假设操作的准确性。以矩阵求逆为例，当使用浮点数时，存在7x7阶降秩情况，会导致结果出现难以置信的误差。如果使用任意精度算术，则这些算法不再是恒定时间的。如果由于数字表示而导致实现给出错误答案，则它不是真正的实现。 - hutch

Answer 5

如果你考虑Brainfuck或图灵机本身，那么有一个基本操作需要O(n)的时间，尽管在大多数其他语言中可以在O(1)的时间内完成——索引数组。

我不完全确定这一点，但我认为在函数式编程中也不能真正拥有数组（具有O(1)“获取位置元素”和O(1)“设置位置元素”）。由于不可变性，你可以拥有一个可以快速更改的结构，但访问它需要时间，或者你将不得不在每次更改时复制大量结构以获得快速访问。但我猜你可以使用单子来欺骗它。

- svick

---

你可以使用任何一种分析方法来作弊，以检测出数组被使用的方式，一旦更新后，旧版本就再也不会被触及。虽然你无法检测到所有这种用法模式的实例，但如果至少有一些情况是可以识别的，那么你可以让编译器生成在这些情况下进行O(1)原地变异的代码。Monad是一个流行的技巧，因为很容易发明一个Monad，使得这种模式非常清晰（通过隐藏“真正”的数组，使用户无法滥用它）。 - mokus

Answer 6

从函数式编程和命令式编程的角度来看，我怀疑你不会发现任何真正的区别。

然而，如果单独看每种语言和实现方式，情况就不同了。暂且不考虑Brainfuck等语言的例子，仍然可以找到一些相当不错的例子。

我仍然记得很多年前在主机上写APL时的一个例子。任务是在一个已排序的数字数组中查找（并消除）重复项。当时，我所做的大部分编程工作都是用Fortran完成的，还有一些用Pascal（当时最新最伟大的东西）或BASIC完成的小片段。我做了一个看起来很明显的事情：编写了一个循环，遍历数组，比较array[i]和array[i+1]，并跟踪一些索引，将每个唯一的元素复制回适当数量的位置，具体取决于已经消除的元素数量。

虽然在我熟悉的语言中这种方法可能效果很好，但在APL中却几乎是一场灾难。更好的解决方案基于APL中易于操作而不是计算复杂性。具体来说，您需要将数组的第一个元素与旋转一个元素后的数组的第一个元素进行比较。然后，您可以将数组保持原样或删除最后一个元素。重复此过程直到整个数组都被遍历（据我回忆，当第一个元素小于旋转数组中的第一个元素时检测到）。

区别相当简单：像大多数APL实现一样（至少在当时），这个实现是一个纯解释器。单个操作（即使是相当复杂的操作）通常非常快，但解释输入文件需要相当长的时间。改进后的版本要短得多，解释速度也更快（例如，APL提供“旋转数组”作为单个原始操作，因此只需解释一个字符或两个字符，而不是一个循环）。

- Jerry Coffin