目录

有没有计算时间复杂度的算法

# 1. Q

一个知乎问题:有没有计算时间复杂度的算法? (opens new window)

输入一段程序,输出这个程序的时间复杂度。这个和停机问题有没有类似之处?

# 2. A

答案是没有。即使输入是一定可停机的程序,也没有。

假设有计算复杂度的程序,那就可以构造出可以判定停机的程序,构造如下:

假设需要判定停机的程序是 P,构造一个程序 H(n),它可以解释运行 P 程序,并执行 n 步后退出。

然后计算 H(n) 的时间复杂度,如果是 O(n),那么 P 是不能停机的,如果是 O(1),显然 P 是可以停机的。

众所周知判定停机的程序不存在,所以计算复杂度的程序也不存在。