O(n^2)
是 O(n^3)
的子集。 维基百科 对此有很好的解释。
事实上,如果 lim |f(x)|/g(x)
小于无穷大(n趋近于无穷大),则 f(n)
属于 O(g(n))
。在这里,它将是
O(1/2*n^2+3n) is in O(n^3)
<=> lim |(1/2*n^2+3n)| / n^3
<=> lim |(n*[n/2 + 3])| / n^3
<=> lim |(n/2 + 3)| / n^2 < infinty
for n to infinity n^2 is allways greater then n/2 so for positiv n this goes against 0
k
和c
,使得f(n)
始终小于k*g(n)+c
(并非对于所有的n
都成立-如果对于一个n0
及其之后的所有数字都成立,则足够)。在这里,您可以选择k=1
和c=0
,因为如前所述,对于正整数n
,n^2
始终小于n^3
。
这里有一个很好的O符号的Veen图示。
lim |(1 / 2n + 3) / n²|
将小于无穷大。但是如果我将 g(x) 设为 n²。那么它将变成 lim |(1/2*n^2+3n) / n^2|
,并且这也将小于无穷大。现在,我错在哪里了? - KhiladiBhaiyyaO(n^2)
。O(n^3)
中也包含了所有O(n^2)
的函数,所以这个没有问题。通常情况下,O(n^x)
中包含了所有最高次项为O(n^x)
或小于x
的函数。 - CilencoO
符号并不是一个严格的边界(我们最感兴趣的地方)。实际上,它只是最坏情况下的上限。如果我们想要一个严格的边界,我们必须使用Theta
符号,这是问题中的第三个选项。请参见我编辑后答案中的图片。 - Cilenco首先,我建议不要将渐进界限视为计算机科学的一部分;它是一种数学工具。不要将“大O符号”严格与“最坏情况”等联系起来。大O符号给出了一个渐进上界。就是这样。在计算机科学中,它恰好用于描述算法的最坏情况运行时间,但这是数学而不是计算机科学所描述的。
但这只是我的意见,要注意。
以下是 Big O 符号的定义(这是我最先学习到的正式定义):
来自算法导论第三版(我也正在通过这本书学习算法),第47页:
观察大O符号表示一个集合,因此它可以是一个更大的超集的一部分,并且可以是其他子集的超集。写成“n = O(n)”只是一个形式上不正确的说法,即函数f(n) = n是集合O(n)(n ∈ O(n))的成员。对于给定的函数 g(n),我们用 O(g(n)) [...] 表示函数集合
O(g(n)) = { f(n) : 存在正常数 c 和 n0,使得对所有 n ≥ n0,都有 0 ≤ f(n) ≤ cg(n) }。
那么,你想知道为什么像n2 = O(n3)这样的东西吗?让我们通过我们的正式定义来展示:
g(n) = n3
f(n) = n2
对于所有n ≥ n0,都有0 ≤ n2 ≤ cn3
直观地说,我们可以很容易地看出这个不等式必须存在一些c和n0(实际上,c ≥ 1且n0= 0)才能成立,因为一个三次函数增长的渐近速度比一个二次函数要快。
对于g(n) = n2也是同样的道理,你会看到n2 = O(n2)同样成立(对于c ≥ 1和n0= 0)。
所以,n2 = O(n3) 并且 n2 = O(n2)?这是可能的,因为O(n3)和O(n2)不是不相交的;O(n2)是O(n3)的子集,因为每个二次函数都可以被上界为一个三次函数。
正如你所看到的,渐近界限不一定是紧密的; n = O(n65536)是真实的。然而,显然更喜欢紧密的界限。
如果你能证明它是O(n^2)
(为了证明它是Big Theta(n^2)
,你必须这样做。不要仅仅通过“看它”来做,要进行数学计算),那么在证明中将所有出现的n^2
替换为n^3
。
这个证明还正确吗?
记住,大O表示上界。
T(n) = O(n^2) <=>
存在常数 c > 0, n0 >= 0
,使得对于所有的 n >= n0
,都有 T(n) <= c.n^2
。
现在,c.n^2 <= c.n^3
对于所有的 n > 1
成立(一个恒等式)
=> T(n) <= c.n^2 <= c.n^3
对于所有的 n >= n1 = max(n0, 1)
=>
存在常数 c > 0, n1 = max(n0, 1)
,使得 T(n) <= c.n^3
=> T(n) = O(n^3)
n>=2
(例如使用归纳法),T(n)=O(n^2) => T(n)=O(n^k)
。
O(n)
是最好的情况,接下来是大ThetaO(n^2)
是平均情况,最后,大ohO(n^3)
是最坏的情况。这就是为什么它们都是正确的。因为对于所有输入,该函数最多可以是O(n^3)
,最少为O(n)
。 - MichaelMMeskhi