有没有计算时间复杂度的算法
# 1. Q
一个知乎问题:有没有计算时间复杂度的算法? (opens new window)
输入一段程序,输出这个程序的时间复杂度。这个和停机问题有没有类似之处?
# 2. A
答案是没有。即使输入是一定可停机的程序,也没有。
假设有计算复杂度的程序,那就可以构造出可以判定停机的程序,构造如下:
假设需要判定停机的程序是 P,构造一个程序 H(n),它可以解释运行 P 程序,并执行 n 步后退出。
然后计算 H(n) 的时间复杂度,如果是 O(n),那么 P 是不能停机的,如果是 O(1),显然 P 是可以停机的。
众所周知判定停机的程序不存在,所以计算复杂度的程序也不存在。