算法来估算时间的另一个算法

Question

的复杂性是可以开发一种算法来估算另一种算法的时间复杂度？我的意思是，输入的是一些算法，输出可能是它的时间复杂度（大哦，大欧米茄，等等）。我在网上找不到任何关于它的信息。

谢谢

Answer 1

让我延长@ interjay的评论一点点。

的halting problem是要求

如果能够设计一个图灵机（您可能觉得它在你的计算机的程序），从而给出一个图灵机（同样，认为它作为一个程序）它可以决定这个输入图灵机是否会最终终止。

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

以上说法被称为“减量化”，这是最流行的方式来显示一个给定的问题是无法解决的。