algorithm - 以编程方式获得代码的Big-O效率

Question

我想知道是否有自动确定(至少粗略地)给定函数的 Big-O 时间复杂度的方法？

如果我绘制 O(n) 函数与 O(n lg n) 函数的图表，我想我可以直观地确定哪个是哪个；我认为必须有一些启发式解决方案可以自动完成此操作。

有什么想法吗？

编辑:我很高兴找到半自动解决方案，只是想知道是否有某种方法可以避免进行完全手动分析。

Answer 1

听起来您要求的是暂停问题的扩展。我不相信这样的事情是可能的，即使在理论上也是如此。

只是回答“这行代码会运行吗？”这个问题在一般情况下，即使不是不可能，也是非常困难的。

编辑添加:虽然一般情况是棘手的，但请参阅此处的部分解决方案:http://research.microsoft.com/apps/pubs/default.aspx?id=104919

此外，有些人表示手动进行分析是唯一的选择，但我认为这并不是真正正确的看待它的方式。即使将人添加到系统/机器中，棘手的问题仍然是棘手的。经过进一步思考，我认为 99% 的解决方案可能是可行的，甚至可能与人类一样好或更好。