编程方式获取大O效的代码
https://stackoverflow.com/questions/480775
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我不知道是否有任何自动的方式的决定(至少大致)的大O时间的复杂程度给予的功能？
如果我绘制一个O(n)与功能O(n lg n)的功能，我认为我就可以直观地确定其是其中；我想必须有一些启发的解决方案，这使得这个是自动完成的。
任何想法？
编辑： 我很高兴找到一个半自动化解决办法，只是想知道是否有某种方式避免这样做完全手册》分析。
解决方案
这听起来像你问的是停机问题的一种推广。我不相信这样的事情是可能的，甚至在理论上。
只是回答这个问题：“请问这行代码永远运行？”将是非常困难的，如果不是不可能在一般情况下这样做。
编辑补充： 虽然一般情况下是顽固性，在这里看到的部分解决方案： HTTP：/ /research.microsoft.com/apps/pubs/default.aspx?id=104919
此外，有些人说，做手工分析是唯一的选择，但我不相信这是真的看它的正确方法。一个棘手的问题仍是棘手的，即使当一个人被添加到系统/机器。经过进一步反射，我想是有99％的溶液可以是可行的，并且甚至可能工作以及或优于人类。
其他提示
您可以运行该算法在不同大小的数据集，然后你可以使用曲线拟合拿出一个近似值。 （只是看你创建可能会在大多数情况下是足够的曲线，但任何统计软件包有曲线拟合）。
请注意，某些算法表现出一种形状，小的数据集，但另一大...和的大的定义仍然有点模糊。这意味着，具有良好的性能曲线的算法可以有这么多的真实世界开销（用于小数据集），它不会因为理论上更好的算法正常工作。
至于代码检查技术，没有存在。但是，插装你的代码在不同长度运行并输出一个简单的文件（RunSize运行长度就足够了），应该很容易。生成正确的测试数据可能更加复杂（有些算法工作更好/更差与部分有序的数据，所以你想生成的代表您的正常使用情况下的数据的）。
由于与定义的问题“什么是大”而事实上，性能依赖于数据，我发现，静态分析往往是一种误导。当优化性能和两种算法之间进行选择，现实世界“橡胶碰到路面”试验是唯一的最终仲裁器我信任。
一个简单的回答是的这是不可能的，因为不管常量
例如，我可以写在O((n^3/k) + n^2)运行的功能。这简化到为O（n ^ 3）因为当n接近于无穷大时，n^3术语将主导功能，而不管恒定k的。
然而，如果k是在上面的例子中的功能非常大的，该函数将出现在运行几乎完全n^2直到一些交叉点，在该n^3术语将开始占主导地位。因为不断k将是未知的任何分析工具，这将是不可能知道究竟有多大的数据集与测试目标的功能。如果k可以任意大，你不能编制测试数据来确定大哦运行时间。
我很好奇，为什么它是你希望能够做到这一点。根据我的经验，当有人说：“我想，以确定该算法的运行时间复杂性”，他们并没有要求什么，他们认为他们都在问。你最有可能问的是什么是可能的数据这样的算法的现实表现。计算功能的大澳是合理实用的，但也有许多方面可以改变实际使用的算法没有什么比仪表和测试的“实际运行时的性能。”
例如，下面的算法具有相同的准确大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是具有窄范围的工具。这是很有用处的，如果你是深深的算法分析里面，或者如果你正在尝试的证明的一些有关的算法，但如果你正在做的商业软件开发证明是在布丁，你会想拥有实际性能数字，以做出明智的决策。
干杯！
我惊讶地看到这么多尝试的权利要求一个可以"的措施"的复杂性，通过一个秒表。有几个人已经给出正确的答案，但我认为仍有空间来推动重要的一点回家。
算法的复杂性不是一个"程序"的问题；这是一个"计算机科学"的问题。回答这个问题需要分析代码的数学家，使计算的很大-O复杂程度实际上是一种形式的数学证明。它需要一个非常强大的理解的基本计算机操作的，代数，也许是微积分(限制)和逻辑。任何数量的"测试"可以取代对这一进程。
停止一问题的适用，所以复杂的算法是根本无法判定由一个机。
该限制的自动化工具的适用, ，因此也许可以编写程序，以帮助，但它只能帮助约为计算器，帮助一个人的物理作业，或作为多重构浏览器有助于重新组织代码的基础。
任何人认真考虑编写这样的一个工具，我建议以下行使。选择一个合理的简单的算法，如你最喜欢的排序，因为你的问题的算法。获得一个坚实的基准(订的，基于网络的教)领导的过程的计算，算法的复杂性和最终的"大-O"。文件你的步骤，结果如你所经历的过程与你的主题的算法。执行步骤和文献您的进展几个方案，例如最好的情况下，最坏的情况下，且平均情况。一旦你完成，审查文档，并问自己是什么，它将采取编写程序(工具)以为你做它。可以这样做？有多少实际上是自动的，并且多少将仍然是手动？
最良好的祝愿。
这可以为简单的算法工作，但对于为O（n ^ 2 LG n）的，或者为O（n ^ LG 2 N）？
您可以得到视觉上当很容易。
，如果它的一个非常糟糕的算法，也许它不会返回即使在N = 10。
证明，这是不可判定：
假设我们有其中确定一些算法HALTS_IN_FN（程序，函数）是否在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））对任何F（N）不会暂停。如果HALTS_IN_FN返回false，则程序暂停在O（1）时间。
因此，我们有一个矛盾，一个矛盾，并因此程序是不可判定。
我认为这几乎是不可能自动执行此操作。请记住，O（G（N））是在最坏情况下的上限和许多功能进行了大量的数据集的执行比这更好。你必须找到以比较它们在最坏情况下的数据为每一个设定。这本身就是一个艰巨的任务很多算法。
杰弗里大号Whitledge是正确的。从停机问题的简单减少证明这是不可判定...
另外，如果我能写这个程序，我会用它来解决P VS NP，并有100万$。B - ）
这是很多人都评论说，这在理论上是一种固有的无法解决的问题。不够公平，但除此之外，即使解决它对于任何但是最简单的情形似乎是非常困难的。
假设你有具有一组嵌套循环，各自基于在阵列中的项目数的程序。为O（n ^ 2）。但是，如果内环仅在非常具体的情况下运行？说，平均而言，它在aprox的日志（n）的情况下运行。突然，我们的 “明明” 为O（n ^ 2）算法是真正为O（n log n）的。写一个程序，可以确定该内环将被运行，以及多久，潜在地比原始问题更加困难。
记住O（N）是不神;高常数能够而且将会改变游戏场所。快速排序算法为O（n log n）的，当然，但当递归变得足够小，说下降到20项左右，快速排序会改变战术，以一个独立的算法，因为它实际上是更快地做了不同类型的排序的许多实现，说较差O（N），但更小的常数插入排序。
所以，了解你的数据，作出明智的猜测和测试。
好吧，既然你不能证明功能是否停止，甚至，我觉得你问的有点多。
否则@Godeke有它。
您还必须在运行这样的基准时要小心。有些算法会有严重依赖于输入型行为。
以快速排序例如。这是最坏情况的O（N²），但通常O（nlogn）。对于相同尺寸的两个输入。
旅行商是（我想，不知道）O（N²）（编辑：正确的值为0（N）为强力algotithm 的），但大多数算法得到相当不错的近似解决方案更快。
这意味着，该基准结构具有的大部分时间在特设的基础上进行调整。想象一下，写的东西一般所提到的两个例子。这将是非常复杂的，可能无法使用，可能无论如何都会被给予不正确的结果。
我想这是不可能在完全自动的方式，因为输入的类型和结构的不同函数之间的很多。
我不知道什么是在这样的目标，但我们的课程我在教学中也有类似的问题。学生们被要求执行的东西，在一定复杂性的工作。
为了不手动去对其的解决方案，并读取它们的代码中，我们使用@Godeke建议的方法。其目的是找到谁使用链接，而不是一个balansed搜索树列表（即不要求的复杂工作，即实现 - 但没有实际阅读他们的代码）的学生，或谁实现冒泡排序，而不是堆排序的学生。
出人意料的是，结果并没有透露是谁欺骗学生。这可能是因为我们的学生是诚实的，想了解（或只知道，我们会检查这个;-)）。这是可能错过作弊的学生，如果输入的是小的，或者如果输入本身是有序的还是这样。这也可能是错的谁没有作弊的学生，但有大的恒定值。
但是，尽管可能出现的错误的，这是非常值得的，因为这样可以节省大量时间检测的。
我使用适合于对执行时间变化的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)
--------------------------------------------------------------------------------
如果你有大量的homogenious计算资源，我想次地对几个样品，做线性回归，然后简单地取最高项。
可以很容易地得到的指示（例如“是函数线性？子线性？多项式？指数”）
这是很难找到确切的复杂性。
例如，这里有一个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)]
