未知算法的大O [英] Big O of unknown algorithm

问题描述

我得到了一个未知的算法，我需要计算的时间复杂度（大O）。 我知道该算法的唯一的一点是它需要多长时间来完成其计算值的给定数。 只是要清楚，该算法采取了许多，并使用该号码时返回的时间。

使用所需的时间，并给出了当时的数字，我得到一个近似直线，如果我做对给出的数字所花费的时间的关系图。该生产线非常适合于 0的复杂性（N日志N）。问题仍然是，即使该行倒是可以，我不能证明这种复杂性确实是 N日志ñ。那么，如何能证明的复杂性？

下面是一些值：

 时间：0.008几个要素：4000
时间：0.100几个要素：40000
时间：0.1200几个要素：400000
时间：1.4000几个要素：4000000
 

解决方案

的意见是对的：你不能的证明的复杂性，并且需要更多的点，它实证模型。这可以从当前数据中的情节。

如果你得到更多的数据，有一件事情你可以做调查这是一个双对数图的，正绘制的时间t的对数元素的数目的对数。这使您梯度P A直线上，如果你们的关系是形式：T已= N ^ P，如下图所示的一些模拟数据。黑点是AY = X ^ 2的关系，绿色为Y = X，和红色为Y = X *日志（x）是某处插图中。

如果你认为这是一个nlogn关系，你可以简单地绘制T压nlogn，你应该得到一条直线。回归分析当然是可能的，但如果你看看你现在的数据，你实际上得到一个线性回归（在第一条曲线如上图所示）很好的直线拟合，我当然不会说这是线性的基础上，

I got an unknown algorithm that I need to calculate the time complexity for (Big O). The only thing that I know about the algorithm is how long it takes to finish its calculations for a given number of values. Just to make it clear, the algorithm is taking a number and returning the time taken when using that number.

Using the time taken and the numbers given for that time, I get a nearly straight line if I make a plot of the time taken against the numbers given. The line fits well to the complexity of O(n log n). The problem is still that even if the line does fit, I can't prove that the complexity really is n log n. so How can I prove the complexity?

Here are some values:

time: 0.008  number of elements: 4000
time: 0.100  number of elements: 40000
time: 0.1200 number of elements: 400000
time: 1.4000 number of elements: 4000000

解决方案

The comments are right: you can't prove the complexity, and you need more points to model it empirically. This is shown by the plot of your current data.

If you get more data, one thing you could do to investigate it is a log-log plot, plotting the log of time t against the log of number of elements n. This gives you a straight line with gradient p if your relationship is of the form: t = n^p, as illustrated below with some simulated data. The black points are for a y=x^2 relationship, the green for y=x, and the red for y=x*log(x) is somewhere inbetween.

If you think it's an nlogn relationship, you could simply plot t against nlogn, and you should get a straight line. Regression analysis is certainly possible, but if you look at your current data, you actually get a very good straight line fit from a linear regression (shown on the first plot above), and I certainly wouldn't say that it's linear on that basis.

这篇关于未知算法的大O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！