以编程方式获取代码的大O效率

Question

以编程方式获取代码的大O效率

algorithmcomplexity-theory

43

我想知道是否有一种自动确定给定函数的大O时间复杂度（至少是粗略的）的方法？

如果我将O(n)函数与O(n log n)函数绘制在图表上，我认为我能够直观地确定哪一个是哪一个；我正在思考是否有某种启发式解决方案可以自动完成这个过程。

有什么想法吗？

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

- kronoz

2

你可以尝试在Rentacoder上找人来做，就像他们用停机问题一样 :) - Tamas Czinege

啥？哈哈——哇，那些 Rentacoders 真是顶尖啊，不是吗？=P - Erik Forbes

如果您只需要对一些样本数据进行多项式拟合，那么这里有一个例子https://dev59.com/OnRB5IYBdhLWcg3w7riV（请参见帖子末尾的源代码链接）。 - jfs

18个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- helcode · Answer 1

我正在使用一个big_O库(链接在此处)，它将执行时间的变化对独立变量n进行拟合，以推断增长阶级O()。

该软件包通过测量收集数据与每个类的增长行为之间的残差来自动建议最佳拟合类。

检查此答案中的代码。

输出示例：

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)
--------------------------------------------------------------------------------

- Brian Postow · Answer 2

Jeffrey L Whitledge 是正确的。从停机问题的简单归约证明了这是不可判定的...

此外，如果我能编写这个程序，我会用它来解决 P vs NP 问题，并获得100万美元... B-)

- Jason Orendorff · Answer 3

正如其他人所说，这在理论上是不可能的。但在实践中，只要你不介意有时会出错，你就可以对一个函数是否为O(n)或O(n^2)做出有根据的猜测。

首先运行算法，将其应用于各种n的输入。在对数-对数图表上绘制点。通过这些点画出最佳拟合线。如果该线很好地适配了所有点，则数据表明该算法是O(n^k)，其中k是该线的斜率。

我不是统计学家。你应该对此持保留态度。但我实际上已经在自动化性能回归测试的背景下做过这件事。这里的补丁包含一些JS代码。

- mooware · Answer 4

我猜这不可能以完全自动化的方式实现，因为函数输入的类型和结构差异很大。

- George IV · Answer 5

嗯，既然你无法证明一个函数是否会停止，我认为你要求有点过分了。

否则@Godeke已经解决了这个问题。

- Anna · Answer 6

我不知道你在做这件事情的目的是什么，但我们在我教授的一门课程中遇到了类似的问题。学生们需要实现一个在特定复杂度下工作的东西。

为了不手动检查他们的解决方案并阅读他们的代码，我们使用了@Godeke建议的方法。目标是找到使用链表而不是平衡搜索树的学生，或者实现冒泡排序而不是堆排序的学生（即不符合所需复杂度的实现 - 但不必实际阅读他们的代码）。

令人惊讶的是，结果没有揭示出作弊的学生。这可能是因为我们的学生诚实并且想要学习（或者只是知道我们会检查这个;-)）。如果输入很小，或者输入本身是有序的等等，就有可能错过作弊的学生。也有可能对没有作弊的学生产生误判，但尽管可能存在这些错误，它仍然非常值得，因为它可以节省大量的检查时间。

- Dmitri Nesteruk · Answer 7

如果您有大量同质的计算资源，我建议您对几个样本进行时间测量并进行线性回归，然后选择最高项。

- orip · Answer 8

获取指示很容易（例如，“函数是线性的吗？亚线性的？多项式的？指数的？”）

找到确切的复杂度很难。

例如，这里有一个Python解决方案：您提供函数和创建其大小为N的参数的函数。您将获得要绘制或执行回归分析的(n，时间)值列表。它会计时一次以获得速度，要获得真正好的指示，需要多次计时以最小化环境因素的干扰（例如使用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)]