我不知道是否有确定的（至少大约）给定函数的大澳时间复杂度的任何自动方式？

I wonder whether there is any automatic way of determining (at least roughly) the Big-O time complexity of a given function?

如果我绘制一个O（n）函数与为O（n LG电子n）函数，我认为我能直观地确定哪个是哪个;我想一定是有启发性的解决方案，使这是自动完成的。

If I graphed an O(n) function vs. an O(n lg n) function I think I would be able to visually ascertain which is which; I'm thinking there must be some heuristic solution which enables this to be done automatically.

任何想法？

编辑：我很高兴找到了半自动化的解决方案，只是不知道是否有避免做全手动分析的一些方法

I am happy to find a semi-automated solution, just wondering whether there is some way of avoiding doing a fully manual analysis.

推荐答案

这听起来像你所要求的是什么停机问题的延伸。我不相信这样的事情是可能的，甚至在理论上。

It sounds like what you are asking for is an extention of the Halting Problem. I do not believe that such a thing is possible, even in theory.

刚回答这个问题：请问这行code永远跑？将是非常困难的，如果不是不可能做在一般情况下

Just answering the question "Will this line of code ever run?" would be very difficult if not impossible to do in the general case.

编辑补充： 虽然一般情况下是棘手，在这里看到了部分解决方案：http://research.microsoft.com/apps/pubs/default.aspx?id=104919

Edited to add: Although the general case is intractable, see here for a partial solution: http://research.microsoft.com/apps/pubs/default.aspx?id=104919

此外，有些人说，做手工分析是唯一的选择，但我不相信这是真的看它的正确方法。一个棘手的问题仍是棘手的，即使一个人被添加到系统/机器。经过进一步的思考，我想，一个99％的解决方案可能是可行的，甚至可能工作以及或好于人类。

Also, some have stated that doing the analysis by hand is the only option, but I don't believe that is really the correct way of looking at it. An intractable problem is still intractable even when a human being is added to the system/machine. Upon further reflection, I suppose that a 99% solution may be doable, and might even work as well as or better than a human.