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

Question

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

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

有什么想法吗？

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

- kronoz

---

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

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

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

Answer 1

听起来您要求的是Halting问题的扩展。即使从理论上讲，我也不认为这种事情是可能的。

仅仅回答“这行代码是否会运行？”在一般情况下会非常困难，甚至是不可能的。

编辑添加： 虽然一般情况下是棘手的，但是在此处可以看到部分解决方案：http://research.microsoft.com/apps/pubs/default.aspx?id=104919

另外，有人声称手动分析是唯一的选择，但我认为这并不是正确的看法。即使人类被加入到系统/机器中，一个棘手的问题仍然是棘手的。进一步反思后，我想一个99%的解决方案是可行的，并且可能会像或比人类表现得更好。

- Jeffrey L Whitledge

---

是的，指出这一点非常重要。尽管如此，仍然存在半自动化的解决方案，正如OP所述，他对此感到满意。 - Noldorin

我在哪里可以找到半自动化的解决方案？我想看一个，因为我还没有能够想象出来。 - David Thornley

停机问题只有在以下情况下才是问题： 1）您的函数可能进入一个永远无法完成的状态。（希望您的生产代码不会落入此类别）。

• 并且 - 2）通过查看代码，您的分析器无法确定#1是否适用于您的函数。

- mbeckish

我相信那就是问题的定义。 =P - Erik Forbes

“停机问题”确实适用，因为有时候不可能确定大O表示法（因为你可能无法证明函数是否会完成）。然而，我们经常进行手动的大O分析。停机问题并不意味着我们永远无法做到这一点。它指的是存在某些程序无法进行这种分析，这是一个重要的区别。如果提问者想比较几个可停止的算法，则可以使用实证数据估计大O，而不是进行手动分析。 - Adrian McCarthy

Answer 2

您可以运行算法以处理各种大小的数据集，并使用曲线拟合得出近似值。（通常仅查看所创建的曲线即可，但任何统计软件都具有曲线拟合功能）。

请注意，某些算法在小型数据集上呈现一种形态，在大型数据集上则呈现另一种形态......而“大型”定义还有点模糊。这意味着一个性能曲线良好的算法可能存在太多真实世界的开销，因此（对于小型数据集）其效果不如理论上更好的算法。

至于代码检查技术，目前还不存在。但是，将您的代码进行工具化，使其在各种长度上运行并输出简单的文件（RunSize RunLength就足够了）应该很容易。生成适当的测试数据可能会更加复杂（有些算法在部分有序数据中表现得更好/更差，因此您需要生成代表正常用例的数据）。

由于“大”的定义问题以及性能与数据相关，我发现静态分析通常会误导人。在优化性能和选择两个算法之间时，真实世界中的“实践检验”测试是我唯一信任的最终仲裁者。

- Godeke

---

我没有点踩，但曲线拟合方法最多只能猜测算法的大O复杂度。当你扩大问题规模到比你的样本大几个数量级时，很可能会出现错误。 - Stephen C

请注意，一些算法在小数据集上表现出一种形状，但在大数据集上表现出另一种形状...而“大”的定义仍有点模糊。正确推导的大O公式告诉您算法在N变得非常大时的行为方式。如果您准备好进行数学计算，还可以以其他方式描述算法；例如，对于小N、平均/最佳情况/最坏情况、多个参数等。 - Stephen C

发帖者要求“自动方式”来进行这样的决策。除非您已经解决了停机问题（请分享！），否则没有自动化方法。我建议曲线拟合是最接近自动化的方法，特别是因为您可以在您预计处理的问题规模上绘制各种算法选择的图形并扩展处理。我提出这个建议是因为原始发帖者对分析方法不感兴趣，而是想要一个自动化的方法。 - Godeke

顺便提一下，我经常发现在实践中，算法上更优的解决方案实际上会因为反映实现效率的那个讨厌的常数而变得更慢。例如，最好的排序算法是混合使用简单方法，直到达到特定递归深度时，它们才使用更“昂贵”但“算法上更好”的解决方案。 - Godeke

Answer 3

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

例如，我可能会编写一个运行时间为O((n^3/k) + n^2)的函数。这可以简化为O(n^3)，因为随着n趋近于无穷大，n^3项将支配该函数，无论常量k如何。

然而，如果在上述示例函数中k非常大，则该函数将几乎以n^2的速度运行，直到某个交叉点，在该交叉点之后n^3项将开始支配该函数。因为常量k对于任何性能分析工具来说都是未知的，所以无法知道要测试目标函数的数据集有多大。如果k可以任意大，你就不能制定测试数据来确定该函数的大O运行时间。

- Triptych

---

很好的观点，不过如果步骤数量已知，可以使用曲线拟合来得到近似答案。 - Joey Robert

这是不可能的。但这个问题仍然有其他解决方法，只是用秒表进行采样不适用。 - Maëlan

Answer 4

我惊讶地看到有这么多人试图通过秒表来“衡量”复杂性。一些人已经给出了正确的答案，但我认为仍然有必要强调基本观点。

1. 算法复杂度不是一个“编程”问题；它是一个“计算机科学”问题。回答这个问题需要从数学家的角度分析代码，因此计算大O复杂度实际上是数学证明的一种形式。这需要对基本的计算机操作、代数、也许是微积分（极限）和逻辑有非常深入的理解。没有任何数量的“测试”可以替代这个过程。

2. 停机问题适用，因此机器根本无法确定算法的复杂性。

3. 自动化工具的限制适用，因此可能会编写一个程序来帮助，但它只能在物理作业中帮助像计算器一样，在重新组织代码库时帮助像重构浏览器一样。

4. 对于任何认真考虑编写这样的工具的人，我建议进行以下练习。选择一个相当简单的算法，比如你最喜欢的排序算法，作为你的主题算法。获得一个可靠的参考资料（书籍、基于Web的教程），引导您通过计算算法复杂度和最终“大O”的过程。随着您进行主题算法的过程，记录您的步骤和结果。执行这些步骤并记录多种情况下的进展，例如最佳情况、最坏情况和平均情况。完成后，审查您的文档，并问自己编写一个程序（工具）需要什么。它能做到吗？有多少会自动化，有多少仍然是手动的？

祝一切顺利。

- Rob Williams

---

好的回答。但即使一个问题是不可判定的，我们也可以尝试解决它的特殊情况，特别是那些具有实际意义的情况。 - user51568

是的，编程和程序员在特殊情况下茁壮成长，即使最难的问题也变得易于处理。 - Rob Williams

Answer 5

我很好奇你为什么想要这样做。根据我的经验，当有人说：“我想确定这个算法的运行时间复杂度”时，他们并不是在问自己认为的问题。你最可能在问的是这样一个算法在实际数据下的真实性能。计算函数的大O符号是有一定用处的，但是在实际使用中，有很多方面会影响算法的“真实运行时间”，所以最好的方法是通过测试和调试来获得答案。

例如，以下算法具有完全相同的大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]

同样是大O表示法...但一个使用行顺序，另一个使用列顺序。由于引用局部性和高速缓存一致性，实际运行时间可能完全不同，特别是取决于数组foo的实际大小。如果算法是软件的一部分，并且内置了一些并发性，那么这甚至无法触及算法的实际性能特征。

不要消极地看待大O表示法，它只是一种具有狭窄范围的工具。如果您深入进行算法分析或尝试证明某个算法的优势，那么它非常有用；但如果您正在进行商业软件开发，则需要实际的性能数据来做出明智的决策。

祝好！

- Eduardo Arino de la Rubia

---

但是随着n的增加，你花费在缓存上的时间也会增加。你的复杂度不会改变，但常数会增加。这并不意味着大O表示法没有用。 - Calyth

@Calyth。不，它并没有说大O是无用的。这就是为什么Earino 没有说大O是无用的，而是说它具有合理的实用性。 - MarkJ

Answer 6

这对于简单算法可能有效，但对于O(n^2 lg n)或O(n lg^2 n)呢？

很容易被视觉上欺骗。

如果是一个非常糟糕的算法，甚至在n=10时都可能无法返回结果。

- Pyrolistical

---

一个算法可以被归类为糟糕的，如果它是由不正确、难以理解或低效的部分组成的组合。如果使用线性时间复杂度的n=10算法（即O(k)，非常理想），这意味着查询的代码不必包含任何循环... - rlb.usa

Answer 7

证明这是不可判定的：

假设我们有一个算法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，则该程序将永远运行，当然不会在任何 O(f(n)) 的时间内停机。如果 HALTS_IN_FN 返回 false，则程序将在 O(1) 时间内停机。

因此，我们得到一个悖论、一个矛盾，因此该程序是不可判定的。

- mindvirus

Answer 8

很多人评论说这个问题在理论上是本质上无法解决的。没错，但除此之外，即使对于除了最微不足道的情况之外的任何情况进行解决似乎也异常困难。

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

请记住，O(N)并不是万能的，高常数会改变游戏规则。快速排序算法当然是O(n log n)，但当递归变得足够小，比如只剩下20个项时，许多快速排序的实现都会改变策略，使用另一种算法，比如插入排序，虽然它的O(N)更差，但常数要小得多。

因此，请理解您的数据，做出合理猜测，并测试。

- Beska

Answer 9

您在运行此类基准测试时也必须小心。一些算法的行为会严重依赖于输入类型。以快速排序为例，它的最坏情况是O(n²)，但通常是O(nlogn)，对于相同大小的两个输入而言。

旅行商问题（我认为，不确定）是O(n²)（编辑：暴力算法的正确值为O(n!)），但大多数算法可以更快地得到相当不错的近似解决方案。

这意味着基准测试结构大部分时间都必须根据需要进行适应。想象一下为这两个示例编写通用内容。它将非常复杂，可能无法使用，并且很可能会提供错误的结果。

- user54579

---

TSP 是 NP 完全问题，只是让你知道。 - Andrew Coleson

一个朴素的旅行商算法是O(n!)，这是超指数级别的，但我认为可能存在只有指数级别O(2^n)的算法。目前没有已知的多项式O(n^2)解决方案。 - Jeffrey L Whitledge

实际上，就算价值不大，O(n!) 实际上是指数级的。 O(n!) = O((n/e)^n) < n^n = 2^(nlogn) < 2^(n^2)，显然是指数级而不是超指数级。事实上，任何 NP 问题都有一个 EXPTIME 算法。 - user51568

有一个时间复杂度为 O(n^3*2^n) 的动态规划算法，其中你填充一个矩阵 M[1 <= i <= n][1 <= j <= n][c_1 = f/t, ..., c_n = f/t] = true 当且仅当存在一条从 i 到 j 的路径，该路径正好使用 c_k = true 的节点 k。 - user51568

Answer 10

我认为自动完成这个任务几乎是不可能的。请记住，O(g(n))是最坏情况的上界，对于许多数据集来说，许多函数的表现要比O(g(n))更好。你需要找到每个算法的最坏情况数据集才能进行比较。这本身对于许多算法来说就是一个困难的任务。

- Kamil Kisiel