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

听起来你要求的是停顿问题的延伸。我认为这样的事情是不可能的,即使在理论上也是如此。

编辑以添加: 尽管一般情况难以解决,但部分解决方案请参见此处: http://research.microsoft.com/apps/pubs/default.aspx?id=104919

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

远至 技术是不存在的。但是检测代码以不同的长度运行并输出一个简单的文件(RunSize-RunLength就足够了)应该很容易。生成正确的测试数据可能更复杂(有些算法对偏序数据的效果更好/更差,所以您可能希望生成 代表您的正常用例 ).

由于“什么是大的”的定义存在问题以及性能依赖于数据这一事实,我发现静态分析通常是误导性的。当优化性能并在两种算法之间进行选择时,真实世界的“橡胶上路”测试是我唯一信任的最终仲裁员。

这是不可能的,因为常数很重要 .

例如,我可以编写一个在中运行的函数 O((n^3/k) + n^2) . 这简化为O(n^3),因为当n接近无穷大时 n^3 无论常数是多少,项将支配函数 k

然而,如果 K 在上面的示例函数中非常大,该函数看起来几乎完全可以运行 n^2 直到某个交叉点 n^3 任期将开始占主导地位。因为常数 K

1. 算法复杂性不是一个“编程”问题;这是一个“计算机科学”问题。回答这个问题需要从数学家的角度分析代码,这样计算Big-O复杂性实际上就是一种数学证明。它需要对计算机的基本运算、代数、微积分(极限)和逻辑有很强的理解。任何数量的“测试”都无法替代该过程。

3. The limits of automated tools applies ,因此,编写一个程序来提供帮助是可能的,但它所能提供的帮助仅相当于计算器帮助完成物理作业,或者重构浏览器帮助重新组织代码库。

4. 对于认真考虑编写这样一个工具的人,我建议进行以下练习。选择一个相当简单的算法,比如你最喜欢的排序,作为你的主题算法。获取可靠的参考资料(书籍、基于网络的教程),指导您完成计算算法复杂度的过程,并最终完成“Big-O”。使用主题算法完成过程时,记录步骤和结果。执行这些步骤并记录几个场景的进度,例如最佳情况、最坏情况和平均情况。完成后,回顾文档,问问自己需要什么来编写一个程序(工具)来为自己完成。能做到吗?有多少是自动的,还有多少是手动的?

最美好的祝福。

我很好奇为什么你想这样做。根据我的经验,当有人说:“我想确定这个算法的运行时复杂性”时,他们并不是在问他们认为他们在问什么。您最可能要问的是,对于可能的数据,这种算法的实际性能如何。计算函数的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]

彻底地 不同的实际运行时,尤其取决于数组foo的实际大小。如果算法是内置有某种并发性的软件的一部分,那么它甚至还没有触及算法行为的实际性能特征。

不是消极的耐莉,但big-O是一个范围狭窄的工具。如果你深谙算法分析,或者你正在尝试这样做,那么它是非常有用的 证明 关于一个算法,但是如果你在做商业软件开发,证据就在布丁里,你需要有实际的性能数据来做出明智的决定。

干杯

这可能适用于简单的算法,但是O(n^2 lg n)或O(n lg^2 n)呢?

你很容易在视觉上被愚弄。

很多人评论说,这在理论上是一个无法解决的问题。这很公平,但除此之外,即使解决除最琐碎的案件以外的任何案件,似乎都是难以置信的困难。

假设您有一个具有一组嵌套循环的程序,每个循环基于数组中的项数。O(n^2)。但是,如果内部循环只在一组非常特定的情况下运行,会怎么样?比如说,平均来说,它是在一个日志(n)案例中运行的。突然,我们的“显然”O(n^2)算法实际上是O(n logn)。编写一个可以确定内部循环是否运行以及运行频率的程序可能比原始问题更加困难。

记住O(N)不是上帝;高常数可以也将改变竞争环境。当然,快速排序算法是O(n logn),但是当递归变得足够小时,比如说减少到20个项目左右,许多快速排序的实现将改变策略为一个单独的算法,因为实际上执行不同类型的排序更快,比如插入排序的O(n)更差,但常数更小。

所以,了解你的数据,做出有根据的猜测,并进行测试。

假设我们在_FN(Program,function)中有一个算法暂停_,它决定了一个程序是否在O(f(n))中对所有n,对某些函数f暂停。

设P为以下程序:

if(HALTS_IN_FN(P,f(n)))
{
    while(1);
}
halt;

由于功能和程序是固定的,因此此输入上的停止时间是恒定的。如果HALTS_IN_FN返回true,程序将永远运行,当然不会在任何f(n)的O(f(n))中停止。如果HOLTS_IN_FN返回false,程序将在O(1)时间内停止。

因此,我们有一个悖论,一个矛盾,因此程序是不可判定的。

我认为这几乎不可能自动完成。请记住,O(g(n))是最坏情况的上界,对于许多数据集,许多函数的性能都优于此上界。为了比较它们,您必须找到每一个的最坏情况数据集。对于许多算法来说,这本身就是一项困难的任务。

杰弗里·惠特利奇是对的。一个简单的停止问题的简化证明了这是不可判定的。。。

而且,如果我能写这个程序,我会用它来解决P对NP的问题,并且有一百万美元。。。B-)

在运行此类基准测试时,您还必须小心。某些算法的行为严重依赖于输入类型。

以快速排序为例。这是最坏的情况O(n),但通常是O(nlogn)。对于相同大小的两个输入。

旅行推销员(我想,不太确定)是O(n²)(

这意味着基准结构在大多数情况下都必须在临时基础上进行调整。想象一下为上面提到的两个例子编写一些通用的东西。它将非常复杂,可能无法使用,而且很可能会给出错误的结果。

我用的是一个 big_O 图书馆( link here )这符合执行时间相对于自变量的变化 n 推断类的增长顺序 O()

该软件包通过测量收集的数据相对于每个类增长行为的残差,自动建议最佳拟合类。

签入代码 this answer .

输出示例,

Measuring .columns[::-1] complexity against rapid increase in # rows
--------------------------------------------------------------------------------
Big O() fits: Cubic: time = -0.017 + 0.00067*n^3
--------------------------------------------------------------------------------
Constant: time = 0.032                                        (res: 0.021)
Linear: time = -0.051 + 0.024*n                               (res: 0.011)
Quadratic: time = -0.026 + 0.0038*n^2                         (res: 0.0077)
Cubic: time = -0.017 + 0.00067*n^3                            (res: 0.0052)
Polynomial: time = -6.3 * x^1.5                               (res: 6)
Logarithmic: time = -0.026 + 0.053*log(n)                     (res: 0.015)
Linearithmic: time = -0.024 + 0.012*n*log(n)                  (res: 0.0094)
Exponential: time = -7 * 0.66^n                               (res: 3.6)
--------------------------------------------------------------------------------

既然你不能证明一个函数是否停止,我想你的要求有点过分了。

我不知道你这样做的目的是什么,但在我教的一门课程中,我们遇到了类似的问题。学生们被要求实现某种在一定复杂度下工作的东西。

为了避免手动查看他们的解决方案并阅读他们的代码,我们使用了@Godeke建议的方法。目标是找到使用链表而不是平衡搜索树的学生,或者实现冒泡排序而不是堆排序的学生(即,在要求的复杂度下不工作的实现,但没有实际阅读代码)。

令人惊讶的是,结果并没有显示作弊的学生。这可能是因为我们的学生是诚实的,想要学习(或者只是知道我们会检查这个;-)。如果输入很小,或者输入本身是有序的,那么可能会错过作弊的学生。对于那些没有作弊,但具有较大常量值的学生来说,也可能是错误的。

但是,尽管可能会出现错误,但这是值得的,因为它节省了大量的检查时间。

正如其他人所说,这在理论上是不可能的。但实际上,你 可以 对一个函数是否为O进行有根据的猜测( N N

第一次的算法,运行它对各种输入 N . 在地图上画点 log-log graph N ^ ),在哪里 K 是直线的坡度。

我不是统计学家。你应该对这一切持保留态度。但我实际上是在性能回归的自动测试环境中做这件事的。 The patch here 包含一些JS代码。

很容易得到指示(例如,“函数是线性的?次线性的?多项式的?指数的”)

很难找到确切的复杂性。

例如,这里有一个Python解决方案:提供函数,以及为其创建大小为N的参数的函数。您将返回一个(n,time)值列表以进行绘图或执行 regression analysis . 它乘以一次速度,为了得到一个真正好的指示,它必须多次计时,以尽量减少环境因素的干扰(例如 timeit 模块)。

import time
def measure_run_time(func, args):
  start = time.time()
  func(*args)
  return time.time() - start

def plot_times(func, generate_args, plot_sequence):
  return [
    (n, measure_run_time(func, generate_args(n+1)))
    for n in plot_sequence
  ]

并使用它进行时间气泡排序:

def bubble_sort(l):
  for i in xrange(len(l)-1):
    for j in xrange(len(l)-1-i):
      if l[i+1] < l[i]:
        l[i],l[i+1] = l[i+1],l[i]

import random
def gen_args_for_sort(list_length):
  result = range(list_length) # list of 0..N-1
  random.shuffle(result) # randomize order
  # should return a tuple of arguments
  return (result,)

# timing for N = 1000, 2000, ..., 5000
times = plot_times(bubble_sort, gen_args_for_sort, xrange(1000,6000,1000))

import pprint
pprint.pprint(times)

这是我的机器上打印的:

[(1000, 0.078000068664550781),
 (2000, 0.34400010108947754),
 (3000, 0.7649998664855957),
 (4000, 1.3440001010894775),
 (5000, 2.1410000324249268)]