我想知道是否可以“编写程序或算法”来查找任何作为输入的给定程序的时间复杂度。
输入：任何程序（P）[以任何语言或特定语言]
输出：该程序的时间复杂度（P）。
之前有没有尝试过编写这样的程序？是否有任何算法可用于此目的？
如果是这样，请提供必要的链接、参考资料或任何可能的指导。
diiva
问问题
10521 次
4 回答
30
不，这是不可能的。这是停机问题的一种形式。
于 2009-09-22T16:33:37.607 回答
4
证明任意算法的复杂性是不可能的，但原则上你可以估计它：
- 选择n，输入的大小
- 运行算法
- 观察 t(n)，为大小为 n 的输入运行算法所需的时间
- 选择另一个 n，重复步骤 2 和 3，直到您有大量数据
- 在 n、n^k、log(n)、n log(n)、n! 或任何其他可能合适的术语上回归 t(n)
- 选择一个具有统计意义的术语并声明它是您估计的算法复杂度
这种方法有很多陷阱
- 这不能证明什么，只能估计
- 如果 t(n) 对于较大的 n 变得非常大，则需要很长时间才能收集足够的数据进行分析
除非您使用巨大的 n 值，否则有很多方法可以欺骗这种方法。例如，这个算法看起来像 O(1)，除非你对 n 使用天文值
sleep for 10 days run an O(n log(n)) sorting algorithm
其他 SO 用户可以想出更多。但在某些情况下，例如当您对算法进行复杂性分析并希望通过经验验证它时，这仍然是一种有用的方法。
于 2009-09-22T17:11:01.890 回答
0
我们不能在算法本身中引入更多变量，并以与我们手动执行相同的方式找到复杂性吗？例如，我们可以在插入排序中有一个变量，比如 n=0，它跟踪算法的整个循环部分，然后给出 O(n^2) 的答案
于 2012-07-25T11:25:09.473 回答
-3
好吧，我认为您可以通过假设所有情况来做到这一点。1：先做一个模块，可以提取每条指令 2：做一个指令数据库，与程序指令相匹配。3：通过获取您在数据库中设置的适当时间复杂度来计算复杂度，仅此而已。
于 2012-04-18T16:30:23.623 回答