问题描述
当我们说一个方法的时间复杂度为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 inO(n)
(trivially)n
is inO(n^2)
(trivially)5n
is inO(n^2)
(starting fromn_0 = 5
)25n^2
is inO(n^2)
(takingk = 25
or greater)2n^2 + 4n + 6
is inO(n^2)
(takek = 3
, starting fromn_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的结果?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!