以编程方式获得代码的 Big-O 效率 [英] Programmatically obtaining Big-O efficiency of code

问题描述

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

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.

只是回答这行代码会运行吗?"的问题.在一般情况下，如果不是不可能的话，那将是非常困难的.

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.

这篇关于以编程方式获得代码的 Big-O 效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！