算法最差的运行时 [英] Worst runtime for an algorithm

问题描述

大家好，

我决定尝试解决有关算法最坏运行时间的问题.
由于我是初学者，所以我想对这项权利有所了解，因此需要一些帮助.

我在使用以下算法的书中提到了这个问题:

输入:一组n点(x1，y1)，. . . ，(xn，yn)且n≥2.
输出:最接近的一对点的平方距离.
ClosePoints

Hello guys,

I decided to try and do a problem about analyzing the worst possible runtime of an algorithm.
Since I''m a beginner and I want to do an understand this right I require some help.

I came accros this problem in a book that uses the following algorithm:

Input: A set of n points (x1, y1), . . . , (xn, yn) with n ≥ 2.
Output: The squared distance of a closest pair of points.
ClosePoints

1. if n = 2 then return (x1 − x2)^2 + (y1 − y2)^2
2. else
3. d ← 0
4. for i ← 1 to n − 1 do
5.....for j ← i + 1 to n do
6. .....t ← (xi − xj)^2 + (yi − yj)^2
7. ......if t < d then
8. .........d ← t
9. return d

这些是问题:
T(n)表示可能的最坏运行时间.
1.证明T(n)= O(n ^ 2).对于这一部分，您必须使用O(·)表示法以及任何
适当的属性.
2.证明T(n)=Ω(n ^ 2). (实际上，对于n
的所有输入，算法的运行时间为Ω(n ^ 2) 点.)
3.可以说T(n)=Θ(n ^ 2)吗?非常简短地说明您的答案.

现在3依赖于1和2.至于1，我知道我们说f是O(g)，发音为
当且仅当存在一个n0∈N并且c> R中的0，这样对于所有
n≥n0我们有
f(n)≤cg(n).
我们也说，如果存在
，则f为Ω(g) n0∈N且c＞ 1. R中的0，因此对于所有n≥n0，我们有
f(n)≥cg(n).

我在考虑使用小的正常数c1，c2，c3，c4 ...来代表执行第1,2,3,4，..行的成本，或者可能只是直接使用O(1)+ O(1) + ...而不是常量....

我应该如何解决问题?
在此先感谢

These are the questions:
T(n) represents the worst possible runtime.
1. Prove that T(n) = O(n^2). For this part you must use the O(·) notation along with any
appropriate properties .
2. Prove that T(n) = Ω(n^2). (In fact the runtime of the algorithm is Ω(n^2) for all inputs of n
points.)
3. Is it true to say that T (n) = Θ(n^2)? Justify your answer very briefly.

Now 3 is dependent of 1 and 2.As for 1 I know that we say that f is O(g), pronounced
if and only if there is an n0 ∈ N and c > 0 in R such that for all
n ≥ n0 we have
f(n) ≤ cg(n).
And also we say that f is Ω(g) if there is an
n0 ∈ N and c > 0 in R such that for all n ≥ n0 we have
f(n) ≥ cg(n).

I was thinking of either using small positive constants c1, c2, c3, c4.... to represent the cost of executing line 1,2,3,4,.. or maybe just directly O(1)+O(1)+...instead of constants....

How should I solve the questions?
Thanks in advance

推荐答案

您正在执行C * n(n - 1)迭代(其中C是一些常数)，产生T(n)=C*n^2 - C*n.

请记住，对于O表示法，我们删除常数因数和低阶项，从而给出O(n)=n^2.

因为您要舍弃常数因子，所以我认为将1、2、3和4表示为O(1)没有任何意义.无论如何，它们都以渐近符号消失.


希望这会有所帮助，
Fredrik Bornander

You''re doing C * n(n - 1) iterations (where C is some constant), yielding T(n)=C*n^2 - C*n.

Remember that for the O notation we drop constant factors and lower order terms giving O(n)=n^2.

Because you''re dropping constant factors I don''t think it makes any sense to represent the 1, 2, 3 and 4 as O(1). They just disappear anyway in the asymptotic notation.


Hope this helps,
Fredrik Bornander

首先，您应该看一下算法要完成多少步.

对于n = 2，它将为1，因为它在第1行终止.

对于n>在图2中，步数由两个嵌套循环确定，并且等于外循环被执行的次数乘以内循环被执行的次数.因此，这将是(n-1)* n.

这些是最好的，同时也是最坏的情况，因为对于任何n＞ 3，这都不会改变. 1

特别是对于n> 2现在您可能已经很容易看到O(n ^ 2)的情况.

To begin with, you should take a look how many steps the algorithm has to take to end.

For n = 2 this would be 1, as it terminates on line 1.

For n > 2 the number of steps is determined by the two nested loops and be equal to the number of times the outer loop is executed times the number of times the inner loop is executed. So this would be (n - 1) * n.

These are the best and at the same time the worst cases, as this does not change for any n > 1

Especially for n > 2 you probably can easily see the realation to O(n^2) by now.

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