Java 如何找到算法的复杂度等级？
我有一个问题要找到算法的复杂性类别估计。该问题给出了算法的记录时间。那么，我是否只是根据计算方式来平均时间？ 抱歉，我漏掉了一部分。 好的，所以它记录的时间如下：N = 100，算法 = 300，下一个 N = 200，算法 = 604，下一个 N = 400 算法 = 1196，下一个 N = 800 算法 2395。所以，我是否计算 300/100，以及604/200 并求平均值。这就是我应该如何估计算法的复杂性类别吗？
I have a question to find a complexity class estimate of a algorithm. The question gives recorded times for an algorithm. So, do I just average out the times based on how it was computed?
Sorry, I missed a part.
ok, so it recorded time like N = 100, Algorithm = 300, next N = 200, Algorithm = 604, next N = 400 Algorithm = 1196, next N = 800 Algorithm 2395. So, do i calculate like 300/100, and 604/200 and find the average. Is that how I'm supposed to estimate the complexity class for the algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
尝试绘制运行时间与 N 的关系图，看看您是否能获得任何见解。 （例如，如果运行时间 = f(N)，f(N) 大约等于 log(N) 或 sqrt(N) 或...？）
Try plotting running time vs. N and see if you get any insight. (e.g. if running time = f(N), is f(N) about equal to log(N), or sqrt(N), or... ?)
我认为时间不会帮助弄清楚它的复杂性类别。即使在完全相同的任务上，时间也可能有很大差异（取决于调度程序或其他因素）。
看看当输入变大时，需要执行多少步。因此，如果您有一个排序算法，需要 100 个步骤来对 10 个项目进行排序，需要 10000 个步骤来对 100 个项目进行排序，那么您会说在大 O ( N^2 ) 中排序，因为
输入步骤
10 100 (等于 10*10)
100 10000 (等于 100*100）
这不是求平均值，而是寻找一个将输入映射到步数的函数，然后找到该函数的哪一部分增长最快（ N^2 比 N 增长得快，所以如果你的函数是 N^ 2 + N 你将其分类为 N^2)。
至少我记得是这样的，但已经过去很多年了！！ :)
编辑：既然你的问题中有更多细节，考虑到上述内容，这就是我要做的。
不要考虑任何平均值，只需考虑 f(100) = 300、f(200)=604 和 f(400)=1196。
而且不必非常精确，只要在大致范围内即可。因此，一个简单的线性函数（例如 f(x)=3*N ），其中 f(100)=300、f(200)=600 和 f(400)=1200 可以描述算法的复杂性算法的复杂度等级是线性的或大 O(N)。
希望有帮助！
I don't think time will help figure out it's complexity class. Times can be very different even on exactly the same task (depends on the scheduler or other factors.)
Look at how many more steps it takes as your input get's larger. So if you had a sorting algorithm that took 100 steps to sort 10 items and 10000 steps to sort 100 items you'd say sorted in big O ( N^2 ) since
Input Steps
10 100 (which equals 10*10)
100 10000 (which equals 100*100)
It's not about averaging but looking for a function that maps the input to the number of steps and then finding what part of that function grows the fastest ( N^2 grows faster than N so if your function was N^2 + N you classify it as N^2).
At least that's how I remember it, but it's been ages!! :)
EDIT: Now that there are more details in your question, here is what I'd do, with the above in mind.
Don't think about averaging anything, just think about how f(100) = 300, f(200)=604, and f(400)=1196.
And it doesn't have to be exact, just in the ball park. So a simple linear function (such as f(x)=3*N ) where f(100)=300, f(200)=600, and f(400)=1200 that would describe the complexity of the algorithm you could say the complexity class of the algorithm was linear or big O(N).
Hope that helps!
它是否也为您提供算法的输入，从而产生记录的时间？您可以根据输入大小与输出运行时间来推断增长顺序。
即输入= 1，运行时间= 10
输入 = 100，运行时间 = 100000
看起来是 O(N^2)
即
输入 = 1 且运行时间 = 10，可能为 O(cn)，其中 C = 10
n = 1、N^2 和 N 相同，
输入 = 10，运行时间 = 100000，可能为 O(cN^2)，其中 C = 10
N = 100*100 = 10000, * 10 = 100000
Does it give you the inputs to the algorithm as well, which produce the recorded times? You can deduce the growth order according to the input size vs output running time.
i.e. input = 1, running time = 10
input = 100, running time = 100000
would appear to be O(N^2)
i.e.
with input = 1 and running time = 10, likely O(cn) where C = 10
with n = 1, N^2 and N are the same
with input = 10 and running time = 100000, likely O(cN^2) where C = 10
and N = 100*100 = 10000, * 10 = 100000
提示：计算算法处理一项的时间。
这些计算时间如何相互关联？
算法是否总是花费相同的时间来处理一项，无论有多少项，是否有一个因素？也许时间呈指数增长？
Hint: Calculate how much time the algorithm spent to process one single item.
How does these calculates time relate to each other?
Does the algorithm alway spent the same time to process one item, regardless how many items, is there a factor? maybe the time raises exponentially?