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

我想知道是否有任何自动方法来确定(至少大致)给定函数的Big-O时间复杂度？

如果我绘制O(n)函数与O(n lg n)函数,我想我能够在视觉上确定哪个是哪个; 我认为必须有一些启发式解决方案,可以自动完成.

有任何想法吗？

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

1> Jeffrey L Wh..：

---

听起来你要求的是延迟停止问题.即使在理论上,我也不相信这样的事情是可能的.

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

编辑添加:虽然一般情况难以处理,但请参阅此处获取部分解决方案:http://research.microsoft.com/apps/pubs/default.aspx？id = 104919

此外,有些人表示,手工分析是唯一的选择,但我不认为这是真正正确的方式.即使将人类添加到系统/机器中,棘手的问题仍然是难以处理的.经过进一步反思,我认为99%的解决方案可能是可行的,甚至可能比人类更好或更好.

---

确实存在暂停问题,因为并不总是可以确定big-O(因为你可能无法证明该函数已经完成).尽管如此,我们一直在进行手动大O分析.暂停问题并没有说我们永远不会这样做.它说有些程序无法完成.这是一个重要的区别.如果提问者正在比较几种停止算法的方法,则可以使用经验数据而不是手动分析来估计big-O.

2> Godeke..：

---

您可以在各种大小的数据集上运行算法,然后您可以使用曲线拟合来得出近似值.(在大多数情况下,仅查看您创建的曲线可能就足够了,但任何统计包都有曲线拟合).

请注意,有些算法表现出一个具有小数据集的形状,而另一个具有较大的数据......并且大的定义仍然有点模糊.这意味着具有良好性能曲线的算法可能具有如此多的实际开销(对于小数据集)它不如理论上更好的算法.

就代码检查技术而言,都不存在.但是检测代码以运行各种长度并输出一个简单的文件(RunSize RunLength就足够了)应该很容易.生成适当的测试数据可能会更复杂(某些算法对部分有序数据的效果更好/更差,因此您需要生成代表正常用例的数据).

由于"什么是大"的定义问题以及性能依赖于数据的事实,我发现静态分析经常会产生误导.在优化性能和在两种算法之间进行选择时,现实世界的"橡胶之路"测试是我信任的唯一最终仲裁者.

---

最有帮助的答案.

---

顺便说一句,我经常发现算法上优越的解决方案在实践中实际上更慢,因为反映实现效率的那个讨厌的常量.例如,最好的排序算法是使用简单方法的混合,直到它们达到特定的递归深度,此时它们使用更"昂贵"但"算法更好"的解决方案.

3> Triptych..：

---

简短的回答是,这是不可能的,因为常数很重要.

例如,我可能会写一个运行的函数O((n^3/k) + n^2).这简化为O(n ^ 3),因为当n接近无穷大时,该n^3术语将主导函数,而不管常数如何k.

但是,如果k在上面的示例函数中非常大,则该函数似乎几乎完全运行,n^2直到某个交叉点,该交叉点将n^3开始占主导地位.因为k任何分析工具都不知道常量,所以不可能知道测试目标函数的数据集有多大.如果k可以任意大,你就不能制作测试数据来确定大的运行时间.

4> earino..：

---

我很好奇为什么你希望能够做到这一点.根据我的经验,有人说:"我想确定这个算法的运行时复杂性",他们并没有问他们认为他们在问什么.您最有可能问的是这种算法对于可能的数据的实际性能.计算函数的Big-O具有合理的实用性,但是有许多方面可以改变实际使用的算法的"实际运行时性能",没有任何东西胜过仪器和测试.

例如,以下算法具有相同的精确Big-O(古怪伪代码):

例子a:

huge_two_dimensional_array foo
for i = 0, i < foo[i].length, i++
  for j = 0; j < foo[j].length, j++
    do_something_with foo[i][j]

例子b:

huge_two_dimensional_array foo
for j = 0, j < foo[j].length, j++
  for i = 0; i < foo[i].length, i++
    do_something_with foo[i][j]

再次,完全相同的大O ...但其中一个使用行常规,其中一个使用列标准.事实证明,由于引用的局部性和高速缓存一致性,您可能有两个完全不同的实际运行时,特别是取决于数组foo的实际大小.如果它是内置一些并发性的软件的一部分,这甚至不会触及算法行为的实际性能特征.

不是负面的,但是大O是一个范围狭窄的工具.如果您深入算法分析,或者如果您正在尝试证明算法的某些内容,那么它非常有用,但如果您正在进行商业软件开发,那么证据就在布丁中,并且您将希望获得实际的性能数据做出明智的决定.

干杯!

5> Rob Williams..：

---

我很惊讶地看到有这么多人试图通过秒表"衡量"复杂性.有几个人给出了正确的答案,但我认为仍有空间将关键点带回家.

算法复杂度不是"编程"问题; 这是一个"计算机科学"的问题.回答这个问题需要从数学家的角度分析代码,这样计算Big-O复杂性实际上是一种数学证明.它需要非常强烈地理解基本的计算机操作,代数,可能是微积分(限制)和逻辑.没有多少"测试"可以代替该过程.

停止问题适用,因此算法的复杂性从根本上说是机器不可判定的.

自动化工具的限制是适用的,所以有可能编写一个程序来帮助,但它只能帮助计算器帮助一个人的物理作业,或者重构浏览器有助于重组一个代码库.

对于任何认真考虑编写此类工具的人,我建议进行以下练习.选择一个相当简单的算法,例如您喜欢的排序,作为主题算法.获得可靠的参考(书籍,基于Web的教程),引导您完成计算算法复杂性的过程,最终获得"Big-O".在使用主题算法完成整个过程时记录您的步骤和结果.执行这些步骤并记录几种情况下的进度,例如最佳情况,最坏情况和平均情况.完成后,请查看您的文档,并问自己如何编写程序(工具)来为您完成.可以吗？实际上会实现多少自动化,还有多少仍然是手动的？

最好的祝愿.