估计另一个算法的时间复杂度的算法

Question

是否可以开发一种算法来估计另一种算法的时间复杂度？我的意思是，输入是某种算法，输出可能是它的时间复杂度(Big-Oh、Big-Omega 等等)。我在网上找不到任何相关信息。

谢谢

Answer 1

让我稍微扩展一下@interjay 的评论。

halting problem在问

if it possible to design a Turing Machine (you may think it as an program in you computer) such that given a Turing Machine (again, think it as a program) it can decide whether or not this input Turing Machine will terminate eventually.

可以证明设计这样的图灵机是不可能的。现在让我们考虑你的问题，如果你能够设计一个算法想要，您将能够回答给定的图灵机是否会终止。不幸的是，这是不可能的。

上述论点称为“归约”，这是表明给定问题无法解决的最流行方式之一。