大o和小o表示法的区别

小开

最佳答案

f∈O(g)表示

对于至少一个选择一个常数k > 0，你可以找到一个常数一个，使得不等式0 <= f(x) <= k g(x)对所有x > a成立。

注意，O(g)是满足这个条件的所有函数的集合。

F∈o(g)表示

对于每一个选择一个常数k > 0，你可以找到一个常数一个，使得不等式0 <= f(x) <K g(x)对所有x > a成立。

同样，注意o(g)是一个集合。

在Big-O中，你只需要找到一个特定的乘数k，它的不等式超过了某个最小值x。

在Little-o中，必须存在最小值x，在此之后，无论k有多小，只要它不为负或零，不等式都成立。

这两个都描述了上界，尽管有点违反直觉，但Little-o是更有力的表述。如果f∈o(g)，则f和g的增长率之间的差距要比f∈o(g)大得多。

这种差异的一个例子是:f∈O(f)为真，但f∈O(f)为假。因此，Big-O可以理解为“f∈O(g)表示f的渐近增长不快于g”，而“f∈O(g)表示f的渐近增长严格慢于g”。就像<=和<。

更具体地说，如果g(x)的值是f(x)的值的常数倍，则f∈O(g)为真。这就是为什么在使用大o符号时可以省略常量。

然而，如果f∈o(g)为真，则g必须在其公式中包含x的更高权力，因此f(x)和g(x)之间的相对间隔必须随着x的增大而增大。

使用纯数学例子(而不是参考算法):

以下是对Big-O是正确的，但如果使用little-o就不正确了:

x²∈O(x²)
x²∈O(x²+ x)
x²∈O(200 * x²)

以下是适用于little-o的情况:

X²∈o(X³)
X²∈o(X !)
Ln (x)∈o(x)

注意，如果f∈o(g)，这意味着f∈o(g)。例如x²∈o(x³)，那么x²∈o(x³)也是成立的，(同样，将o视为<=, o视为<)

小开

Big-O之于little-o，就像≤之于<。Big-O是包容性的上界，而little-o是严格的上界。

例如，函数f(n) = 3n是:

O(n²)， o(n²)，和O(n)
不在O(lg n)， o(lg n)或o(n)中

类似地，数字1是:

≤ 2， < 2，和≤ 1
而不是≤ 0， < 0或< 1

下面是一个表格，展示了大致的想法:

Big o table

(注意:这个表是一个很好的指南，但它的限制定义应该是根据上限而不是正常的限制。例如，3 + (n mod 2)永远在3和4之间振荡。它在O(1)中，尽管没有正常的限制，因为它仍然有lim sup: 4。)

我建议大家记住大o符号是如何转化为渐近比较的。比较更容易记住，但不太灵活，因为你不能说n^{O (1)} = P这样的东西。

小开

我发现当我不能从概念上把握一些东西时，思考为什么要用X对理解x是有帮助的(并不是说你没有尝试过，我只是在设置舞台。)

你知道的:一种常用的算法分类方法是通过运行时，通过引用算法的大复杂度，你可以很好地估计哪一个是“更好的”;——取“最小”的;在O!即使在现实世界中，O(N)也是“更好的”;而不是O(N²)，除了一些愚蠢的东西，比如超大质量常数之类的。

假设有某种算法在O(N)范围内运行。不错吧?但是让我们假设你(你这个聪明的人，你)提出了一个在O(^N / _{loglogloglogN})中运行的算法。耶!它的速度!但是当你写论文的时候，你会觉得一遍又一遍地写这个很傻。所以你写一次，你可以说:“在这篇论文中，我已经证明了算法X，以前可以在时间O(N)内计算，实际上可以在O(N)内计算。”

因此，每个人都知道你的算法更快——快多少还不清楚，但他们知道它更快。从理论上讲。：）

小开

在一般情况下

渐近符号可以理解为:缩小时函数比较如何?(测试它的一个好方法是简单地使用不溶这样的工具并玩鼠标滚轮)。特别是:

f(n) ∈ o(n)意味着:在某一点上，你越缩小，f(n)就越会被n所支配(它将逐渐与它分离)。
g(n) ∈ Θ(n)表示:在某些时候，缩小并不会改变g(n)与n的比较(如果我们从轴上删除刻度，你就无法判断缩放级别)。

最后，h(n) ∈ O(n)意味着函数h可以属于这两个类别中的任何一个。它既可以看起来很像n，也可以在n增加时比n越来越小。基本上，f(n)和g(n)也在O(n)中。

我认为这个维恩图(来自这门课)可以帮助:

在计算机科学领域

在计算机科学中，人们通常会证明一个给定的算法同时承认一个上界O和一个下界𝛺。当两个边界满足时，这意味着我们找到了一个渐近最优算法来解决这个特定的问题Θ。

例如，如果我们证明一个算法的复杂度在O(n)和𝛺(n)中，这意味着它的复杂度在Θ(n)中。(这是Θ的定义，它或多或少地翻译为“渐近相等”。)这也意味着没有算法可以解决o(n)中的给定问题。同样，粗略地说“这个问题不能在(严格地)少于n个步骤内解决”。

通常在下界证明中使用o来表示矛盾。例如:

假设算法A可以在o(n)步中找到大小为n的数组中的最小值。由于A ∈ o(n)，它不能看到输入中的所有项。换句话说，至少有一个x项是A从未见过的。算法A不能区分两个相似的输入实例，其中只有x的值发生了变化。如果x在其中一个实例中是最小值，而在另一个实例中不是，那么A将无法在(至少)其中一个实例中找到最小值。换句话说，在数组中找到最小值是在n0中(在o(n)中没有算法可以解决这个问题)。

下界/上界含义的详细信息

O(n)的上限仅仅意味着即使是在最坏的情况下，算法将在最多n步中终止(忽略所有常数因子，包括乘法和加法)。𝛺(n)的下界是关于问题本身的声明，它说我们构建了一些例子，其中给定的问题不能用任何算法在少于n步内解决(忽略乘法常数和加法常数)。步数最多是n，最少是n，所以这个问题的复杂度“恰好是n”。而不是说“忽略恒定的乘法/相加因子”;每次我们只写Θ(n)。

小开

大o符号有一个同伴叫做小o符号。大o符号表示一个函数是渐近的no more than另一个。为了说一个函数渐近less than另一个，我们使用小o符号。大o和小o符号之间的差异类似于<=(小于等于)和<(不到)。