当某事物是Big O时，是否表示它正是Big O的结果? [英] When something is Big O, does it mean that it is exactly the result of Big O?

问题描述

当我们说一个方法的时间复杂度为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的结果?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！