当我们说一个方法的时间复杂度为O(n^2)时,它的含义与10^2 = 100中的方法相同,还是意味着该方法是 max 或 closest 表示该符号?我对如何理解Big O感到非常困惑.我还记得一个叫做上限的东西,这在最大程度上意味着什么?
When we say a method has the time complexity of O(n^2) is it meant in the same way as in 10^2 = 100 or does it mean that the method is at max or closest to that notation? I am really confused on how to undertand Big O. I remember something called upper bound, would that mean at max?
推荐答案说明
如果方法f在O(g)内部,并且g是另一个函数,则意味着在某个点(存在某些n_0,对于所有n > n_0而言)函数f将始终对于该点,输出的值小于g.但是,允许g具有任意常数k.因此对于某些n_0上方的所有n,f(n) <= k * g(n).因此,允许f首先变大,然后开始变小并保持变小.
Explanation
If a method f is inside O(g), with g being another function, it means that at some point (exist some n_0 such that for all n > n_0) the function f will always output a smaller value than g for that point. However, g is allowed to have an arbitrary constant k. So f(n) <= k * g(n) for all n above some n_0. So f is allowed to first be bigger, if it then starts to be smaller and keeps being smaller.
我们说 f由g 渐近有界. 渐近表示我们不在意f在开始时的行为.接近无穷大时只有它会做什么.因此,我们丢弃n_0以下的所有输入.
We say f is asymptotically bounded by g. Asymptotically means that we do not care how f behaves in the beginning. Only what it will do when approaching infinity. So we discard all inputs below n_0.
一个例子就是这样:
蓝色函数是k * g,具有一些常数k,红色函数是f.我们看到f首先更大,但是从x_0开始,它将始终小于k * g.因此f in O(g).
The blue function is k * g with some constant k, the red one is f. We see that f is greater at first, but then, starting at x_0, it will always be smaller than k * g. Thus f in O(g).
从数学上讲,这可以表示为
Mathematically, this can be expressed by
是Big-O的通常定义.从上面的解释中,定义应该很清楚.它说从某个n_0开始,所有输入的函数f必须小于k * g.允许k为常数.
which is the usual definition of Big-O. From the explanation above, the definition should be clear. It says that from a certain n_0 on, the function f must be smaller than k * g for all inputs. k is allowed to be some constant.
两个图像均来自维基百科.
这里有几个例子可以使您熟悉该定义:
Here are a couple of examples to familiarize with the definition:
- n在O(n)中(平常)
- n在O(n^2)中(平常)
- 5n位于O(n^2)中(从n_0 = 5开始)
- 25n^2位于O(n^2)中(采用k = 25或更高版本)
- 2n^2 + 4n + 6在O(n^2)中(以k = 3,从n_0 = 5开始)
- n is in O(n) (trivially)
- n is in O(n^2) (trivially)
- 5n is in O(n^2) (starting from n_0 = 5)
- 25n^2 is in O(n^2) (taking k = 25 or greater)
- 2n^2 + 4n + 6 is in O(n^2) (take k = 3, starting from n_0 = 5)
实际上,O(g)是数学意义上的集合.它包含具有上述属性(由g渐近限制)的所有函数.
Actually,O(g) is a set in the mathematical sense. It contains all functions with the above mentioned property (which are asymptotically bounded by g).
因此,尽管有些作者写了f = O(g),但实际上是错误的,应该是f in O(g).
So, although some authors write f = O(g), it is actually wrong and should be f in O(g).
还有其他类似的集合,它们仅在绑定方向上有所不同:
There are also other, similar, sets, which only differ in the direction of the bound:
- Big-O:小于等于 <=
- Small-o: less <
- 欧米茄:更大等于 >=
- 小欧米茄:更大 >
- Theta:同时出现Big-O和Big-Omega(等于).
- Big-O: less equals <=
- Small-o: less <
- Big-Omega: greater equals >=
- Small-omega: greater >
- Theta: Big-O and Big-Omega at the same time (equals)
更多推荐
当某事物是Big O时,是否表示它正是Big O的结果?
发布评论