algorithm - 每种算法的最佳时间复杂度要求？

Question

算法的时间复杂度可能因编程语言和实现算法的编程语言而异，因为某些事情不可能用一种语言而不是另一种语言来完成。图灵完备性也没有说明上述语言的时间复杂度可能性。

我的问题是，要使一种编程语言能够以任何语言可能的最佳时间复杂度解决每个算法，有什么要求？图灵完备并添加了在恒定时间内检查/编辑数据结构的可能性就足够了吗？

Answer 1

我认为构建一种可以最佳地解决每个计算问题的单一编程语言或计算模型是不可能的。

在理论计算机科学中有一个结果叫做 time hierarchy theorem这表示对于许多函数 f(n)，有许多问题可以在图灵机上用时间 O(f(n)) 解决，但不能用时间 O(f(n)/log n) 解决。结果的证明基本上是这样工作的:考虑问题“图灵机 M 是否在 f(|w|) 步内拒绝输入 w？”您可以证明您可以在时间 O(f(n)^k) 中确定性地解决这个问题，只需在 w 上模拟 M，执行 f(|w|) 步骤，然后看看会发生什么。但是，如果您解决问题的速度比这“快得多”，那么您可以使用类似停机问题的参数来编写一个程序，询问它是否会在 f( |w|) 步骤，然后执行与预期相反的操作。

我相当有信心，对于任何可行的计算模型，您都可以找到时间层次定理的模拟。例如，假设您有一台类型为 X 的计算机，并考虑“X 是否在 f(|w|) 步内接受 w？”这个问题。 X 型计算机可以解决这个问题，但不能太快，否则会导致矛盾。因此，我们可能会争辩说存在一些函数 a(x) 和 b(x) 使得 X 型计算机可以在时间 O(a(x)) 而不是时间 O(a(x)/b(x))。所以现在去定义一个计算模型 X'，它基本上是 X，但是其中操作“解决问题'X 是否在 f(|w|) 步内接受 w？'”是一个内置操作，需要一个步。现在，这个计算模型 X' 至少可以比 X 更快地解决一个问题。我们可以不断迭代这个构造来构建一个计算模型 X''，它可以比 X' 更快地解决某些问题，一个计算模型 X'' ' 可以比 X'' 等更快地解决某些问题。

因此，我非常有信心您找不到单一的“最佳”计算模型，因为任何计算模型都可以针对自身使用来定义在某些特定输入上比它更快的计算模型. (这在某种程度上与不完备性定理有关 - 任何完备的正式系统都会有一些它无法证明的东西，如果你通过在那个陈述中添加一个轴子来解决这个问题，那么新系统就有一些东西 它无法证明，等等)