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

Question

我想知道是否有任何自动方法来确定（至少粗略地）给定函数的 Big-O 时间复杂度？

如果我绘制一个 O(n) 函数与一个 O(n lg n) 函数，我想我将能够直观地确定哪个是哪个；我认为必须有一些启发式解决方案可以自动完成。

有任何想法吗？

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

score 61 · Accepted Answer

听起来您要求的是停机问题的扩展。我不相信这样的事情是可能的，即使在理论上也是如此。

只需回答“这行代码会运行吗？”这个问题。在一般情况下，即使不是不可能，也将非常困难。

编辑添加：虽然一般情况是棘手的，见这里部分解决方案：http ://research.microsoft.com/apps/pubs/default.aspx?id=104919

此外，有些人说手动分析是唯一的选择，但我不认为这真的是正确的看待它的方式。即使将人添加到系统/机器中，一个棘手的问题仍然是棘手的。经过进一步思考，我认为 99% 的解决方案可能是可行的，甚至可能与人类一样好或更好。

score 39 · Accepted Answer

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

请注意，一些算法在小数据集上表现出一种形状，但在大数据集上表现出另一种形状......而且大的定义仍然有点模糊。这意味着具有良好性能曲线的算法可能具有如此多的现实世界开销，以至于（对于小型数据集）它的效果不如理论上更好的算法。

至于代码检查技术，不存在。但是检测您的代码以各种长度运行并输出一个简单的文件（RunSize RunLength 就足够了）应该很容易。生成正确的测试数据可能会更复杂（某些算法对部分排序的数据效果更好/更差，因此您可能希望生成代表您的正常用例的数据）。

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

score 14 · Accepted Answer

一个简短的回答是这是不可能的，因为常量很重要。

例如，我可能会编写一个在O((n^3/k) + n^2). 这简化为 O(n^3) 因为随着 n 接近无穷大，该项n^3将支配函数，而与常数无关k。

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

score 13 · Accepted Answer

我很惊讶看到有如此多的尝试声称可以通过秒表“测量”复杂性。有几个人给出了正确的答案，但我认为仍有空间将要点带回家。

算法复杂性不是“编程”问题；这是一个“计算机科学”问题。回答这个问题需要从数学家的角度分析代码，因此计算 Big-O 复杂度实际上是一种数学证明形式。它需要对基本的计算机操作、代数、微积分（极限）和逻辑有非常深刻的理解。没有多少“测试”可以替代该过程。
停止问题适用，因此算法的复杂性基本上无法由机器确定。
自动化工具的限制适用，因此可以编写一个程序来提供帮助，但它只能提供与计算器帮助完成物理作业一样多的帮助，或者与重构浏览器帮助重组一个代码库。
对于认真考虑编写此类工具的任何人，我建议进行以下练习。选择一个相当简单的算法，比如你最喜欢的排序，作为你的主题算法。获取可靠的参考资料（书籍、基于网络的教程），引导您完成计算算法复杂度并最终计算“Big-O”的过程。在您使用主题算法完成整个过程时记录您的步骤和结果。执行这些步骤并记录您在几种情况下的进度，例如最佳情况、最坏情况和平均情况。完成后，查看您的文档并问自己编写程序（工具）为您完成它需要什么。可以做到吗？实际上有多少是自动化的，还有多少是手动的？

最良好的祝愿。

score 9 · Accepted Answer

我很好奇为什么你希望能够做到这一点。根据我的经验，当有人说：“我想确定这个算法的运行时复杂性”时，他们并没有问他们认为他们在问什么。您最有可能问的是这种算法对可能数据的实际性能是什么。计算函数的 Big-O 具有合理的实用性，但是在实际使用中，有很多方面可以改变算法的“实际运行时性能”，没有什么比仪器和测试更好的了。

例如，以下算法具有完全相同的 Big-O（古怪的伪代码）：

示例一：

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]

同样，完全相同的 big-O... 但其中一个使用行序数，其中一个使用列序数。事实证明，由于引用的局部性和缓存一致性，您可能有两个完全不同的实际运行时，尤其是取决于数组 foo 的实际大小。如果它是具有内置并发性的软件的一部分，这甚至还没有开始触及算法行为的实际性能特征。

不要成为一个消极的人，但大O是一个范围狭窄的工具。如果您深入了解算法分析，或者如果您试图证明某个算法的某些内容，那么它非常有用，但是如果您正在做商业软件开发，那么证明就在布丁中，并且您将想要获得实际的性能数据做出明智的决定。

干杯!

score 4 · Accepted Answer

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

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

如果它是一个非常糟糕的算法，也许它甚至在 n=10 时也不会返回。

score 3 · Accepted Answer

很多人评论说，这在理论上是一个天生无法解决的问题。很公平，但除此之外，即使解决最微不足道的情况似乎也非常困难。

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

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

因此，了解您的数据，进行有根据的猜测并进行测试。

score 3 · Accepted Answer

证明这是不可判定的：

假设我们有一些算法 HALTS_IN_FN(Program, function) 确定程序是否在 O(f(n)) 中停止对于所有 n，对于某个函数 f。

令 P 为以下程序：

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

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

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

score 2 · Accepted Answer

运行此类基准测试时还必须小心。一些算法将具有严重依赖于输入类型的行为。

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

旅行推销员是（我认为，不确定）O（n²）（编辑：蛮力算法的正确值为0（n！）），但大多数算法更快地获得相当好的近似解。

这意味着基准测试结构在大多数情况下必须在特定的基础上进行调整。想象一下为上面提到的两个例子写一些通用的东西。这将非常复杂，可能无法使用，并且可能会给出不正确的结果。

score 2 · Accepted Answer

我认为自动执行此操作几乎是不可能的。请记住，O(g(n)) 是最坏情况的上限，许多函数的性能优于许多数据集。您必须找到每个数据集的最坏情况数据集才能进行比较。对于许多算法来说，这本身就是一项艰巨的任务。

score 1 · Accepted Answer

Jeffrey L Whitledge 是正确的。停止问题的简单简化证明这是不可判定的......

另外，如果我可以编写这个程序，我会用它来解决 P 与 NP，并有 100 万美元...... B-)

score 1 · Accepted Answer

我正在使用一个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)
--------------------------------------------------------------------------------

score 0 · Accepted Answer

我想这是不可能以全自动方式实现的，因为输入的类型和结构在函数之间有很大差异。

score 0 · Accepted Answer

好吧，既然你无法证明一个函数是否会停止，我认为你的要求有点高。

否则@Godeke 有它。

score 0 · Accepted Answer

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

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

令人惊讶的是，结果并没有发现作弊的学生。这可能是因为我们的学生很诚实并且想要学习（或者只是知道我们会检查这个;-)）。如果输入很小，或者输入本身是有序的，则可能会错过作弊学生。没有作弊但具有较大常数值的学生也可能出错。

但尽管可能存在错误，但还是值得的，因为它节省了大量的检查时间。

score 0 · Accepted Answer

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

第一次算法，在各种n的输入上运行它。在对数图上绘制点。通过这些点绘制最佳拟合线。如果这条线很好地拟合了所有点，那么数据表明该算法是 O( n ^ k )，其中k是线的斜率。

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

score -1 · Accepted Answer

如果你有很多同质的计算资源，我会根据几个样本对它们进行计时并进行线性回归，然后简单地取最高项。

score -1 · Accepted Answer

很容易得到指示（例如“函数是线性的吗？次线性的？多项式？指数的”）

很难找到确切的复杂性。

例如，这是一个 Python 解决方案：您提供函数，以及为其创建大小为 N 的参数的函数。您将返回一个 (n,time) 值列表以进行绘图或执行回归分析。它为速度计时一次，为了得到一个非常好的指示，它必须多次计时以最大限度地减少环境因素的干扰（例如使用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)]

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

18 回答 18

Related

Reference