大 O 表示法究竟代表什么？

Question

大 O 表示法究竟代表什么？

algorithmcomputer-sciencenotationbig-o

218

我对大 O、大 Omega 和大 Theta 记号之间的区别感到非常困惑。

我知道大 O 是上界，大 Omega 是下界，但是大 Theta 到底代表什么？

我读过它表示紧密界限，但是这是什么意思？

- user1364768

可能是下界和紧界的区别？的重复问题。 - Damjan Pavlica

7个回答

105

这意味着算法在给定的函数中同时具有大O和大Ω。

例如，如果它是 Ө(n)，那么存在某个常数 k，使得您的函数（运行时间等）对于足够大的 n 大于 n*k，还有另一个常数 K，使得您的函数对于足够大的 n 小于 n*K。

换句话说，对于足够大的 n，它被夹在两个线性函数之间:

对于 k < K 并且足够大的 n，n*k < f(n) < n*K

- happydave

不是的，那些变量有点混淆，它们之间没有关联。 - Aaron Robeson

@committedandroider 不是的，它们是小写和大写，因此不同，他使用典型的数学风格，在这种风格中，两个“相似”的变量（但在这里没有任何相关性）使用大写和小写。 - Santropedro

16

Theta(n)：如果存在正常数c1和c2，使得函数f(n)夹在c1(g(n))和c2(g(n))之间，则函数f(n)属于Theta(g(n))。即它给出上限和下限。

Theta(g(n)) = { f(n) : 存在正常数c1、c2和n1，使得对于所有n >= n1，0<=c1(g(n))<=f(n)<=c2(g(n)) }

当我们说f(n)=c2(g(n))或者f(n)=c1(g(n))时，表示渐近紧密边界。

O(n)：它只给出上限（可能是紧的也可能不是）

O(g(n)) = { f(n) : 存在正常数c和n1，使得对于所有n>=n1, 0<=f(n)<=cg(n)}

例如:边界2*(n^2) = O(n^2)是渐近紧密的，而边界2*n = O(n^2)不是渐近紧密的。

o(n)：它只给出上界（永远不是紧的）

O(n)和o(n)之间的显着区别是f(n)小于cg(n)，对于所有n>=n1，但不等于O(n)中的情况。

例如:2*n = o(n^2)，但2*(n^2) != o(n^2)

- thisizkp

1

你没有提到大欧米伽，它指的是下限。不过，非常好的第一个答案，欢迎！ - bohney

1

我喜欢他对Theta(n)的定义方式。点赞！ - user720694

将theta视为函数的“平均”时间是否正确？我经常听到人们把它称为平均值，但我不确定它是否真的是平均值，因为它只是受到上下边界的限制。 - berimbolo

7

我希望这是您在经典的CLRS（第66页）中想要找到的内容：

- Lerner Zhang

2

大 O 符号：

不要搞错了，朋友！

假设我们有一个正值函数 f(n) 和一个取正值参数 n 的函数 g(n)，则 ϴ(g(n)) 定义为 {f(n): 存在常数 c1、c2 和 n1，对于所有的 n>=n1}。

其中 c1 g(n)<=f(n)<=c2 g(n)

让我们举一个例子：

假设 f(n)=5n^2+2n+1

g(n)=n^2

c1=5，c2=8，n1=1

在所有符号中，ϴ 符号给出了最好的关于函数增长速率的直觉，因为它给出了一个紧密的界限，而大 O 符号和大 Omega 符号分别给出上确界和下确界。

ϴ 告诉我们，g(n) 的增长速率与 f(n) 的增长速率尽可能接近。

- Ganesh Chowdhary Sadanala

2

首先是理论

大O = 上限 O(n)
Theta = 阶函数 - theta(n)
Omega = Q符号（下限）Q(n)

为什么人们如此困惑？

在许多博客和书籍中，这个语句被强调为：

"这是Big O(n^3)"等等。

人们经常会混淆，比如：

O(n) == theta(n) == Q(n)

但值得记住的是它们只是具有名称O、Theta和Omega的数学函数

因此，它们具有相同的多项式通用公式，

设：

f(n) = 2n4 + 100n2 + 10n + 50，则

g(n) = n4，所以g(n)是一个接受函数作为输入并返回最大幂次变量的函数，

以下所有解释都适用于相同的f(n)和g(n)

Big O(n) - 提供上限

Big O(n4) = 3n4，因为3n4 > 2n4

3n4是Big O(n4)的值，就像f(x)=3x一样

n4在这里扮演着x的角色，所以

将n4替换为x，因此Big O(x')=2x'，现在我们都很满意，通用概念是

所以0≤f(n)≤O(x')

O(x')=cg(n)=3n4

放入数值，

0 ≤ 2n4 + 100n² + 10n + 50 ≤ 3n⁴

3n⁴是我们的上界

Big Omega(n)-提供下界

Theta(n⁴)=cg(n)=2n⁴，因为2n⁴≤我们的示例f(n)

2n⁴是Theta(n⁴)的值

因此，0≤cg(n)≤f(n)

0 ≤ 2n4 ≤ 2n4 + 100n2 + 10n + 50

2n4是我们的下界

Theta(n) - 提供紧密边界

这是计算以确定下界是否类似于上界的过程，

情况1）。上限类似于下限

if Upper Bound is Similar to Lower Bound, The Average Case is Similar

Example, 2n4 ≤ f(x) ≤ 2n4,
Then Theta(n) = 2n4

如果上限与下限不相似，则为第二种情况。

In this case, Theta(n) is not fixed but Theta(n) is the set of functions with the same order of growth as g(n).

Example 2n4 ≤ f(x) ≤ 3n4, This is Our Default Case,
Then, Theta(n) = c'n4, is a set of functions with 2 ≤ c' ≤ 3

希望这解释清楚了！

- Akash

0

我不确定为什么没有简短明了的答案用通俗易懂的英语解释大O符号（好像这就是问题），所以在这里我来解释一下。

大Theta表示函数所需操作增长的范围或确切值（如果大O和大Omega相等）。

- Yehuda Schwartz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

首先让我们了解一下大O、大Theta和大Omega是什么。它们都是函数的sets。

大O给出上界asymptotic bound，而大Omega给出下界。大Theta同时给出上下界。

所有Ө(f(n))的内容也都属于O(f(n))，但反过来则不成立。
如果T(n)既属于O(f(n))，又属于Omega(f(n))，则称其为Ө(f(n))。
在集合术语中，Ө(f(n))是O(f(n))和Omega(f(n))的intersection。

例如，归并排序的最坏情况既是 O(n*log(n)) 又是 Omega(n*log(n)) - 因此也是 Ө(n*log(n))，但它也是 O(n^2)，因为 n^2 渐进地比它更大。然而，它不是Ө(n^2)，因为该算法不是Omega(n^2)。

更深入的数学解释

O(n) 是渐进上界。如果 T(n) 是 O(f(n))，这意味着从某个 n0 开始，存在一个常数 C，使得 T(n) <= C * f(n)。另一方面，大-Omega 表示存在一个常数 C2，使得 T(n) >= C2 * f(n))）。

不要混淆！

不要混淆最坏、最好和平均情况分析：所有三个符号（Omega，O，Theta）都与算法的最坏、最好和平均情况分析无关。每个符号都可以应用于每个分析。

我们通常使用它来分析算法的复杂性（就像上面的归并排序示例）。当我们说“算法A是O（f（n））”时，我们真正意思是“在最坏情况分析下，算法的复杂度是O（f（n））”，这意味着它的规模与函数f（n）类似（或者形式上不比f（n）差）。

为什么我们关心算法的渐进边界？

嗯，有许多原因，但我认为最重要的原因是：

1. 确定精确的复杂度函数更加困难，因此我们在大O/大Theta符号上做出"妥协"，这些符号在理论上已经足够具有信息性。 2. 操作数的确切数量也与平台相关。例如，如果我们有一个包含16个数字的向量（列表），需要多少操作？答案是：取决于不同实现和不同计算机之间的差异，一些CPU允许向量加法，而其他CPU则不允许，这是一种不希望出现的属性。然而，大O符号在不同机器和实现之间更加恒定。为了说明这个问题，请看下面的图表： enter image description here

很明显，f(n) = 2*n 比 f(n) = n 更"糟糕"。但与另一个函数相比，差异并不是非常显著。我们可以看到，f(n)=logn 很快就比其他函数低得多，而 f(n) = n^2 很快就比其他函数高得多。因此，由于上述原因，我们会“忽略”常数因子(例如图表中的2*)，只考虑大O符号。

在上面的例子中，f(n)=n, f(n)=2*n 都属于 O(n) 和 Omega(n) - 因此也属于 Theta(n)。
另一方面，f(n)=logn 属于 O(n)（它比 f(n)=n“更好”），但不属于 Omega(n) - 因此也不属于 Theta(n)。
对称地，f(n)=n^2 属于 Omega(n)，但不属于 O(n)，因此也不是 Theta(n)。

¹通常情况下，虽然不总是如此。当分析类别（最差、平均和最好）缺失时，我们实际上指的是最坏情况。