我正在研究增长"大哦","大欧米茄"和"大the"的订单.由于我不能为这些输入小符号,我将表示如下:
ORDER =大哦
OMEGA =大欧米茄
THETA =大theta
例如,我会说n = ORDER(n ^ 2)意味着函数n的大小为n ^ 2(n最多增长为n ^ 2).
好的,大部分我都明白这些:
n = ORDER(n^2) //n grows at most as fast as n^2
n^2 = OMEGA(n) //n^2 grows atleast as fast as n
8n^2 + 1000 = THETA(n^2) //same order of growth
好的,这个让我困惑的例子:
什么是n(n + 1)vs n ^ 2
我意识到n(n + 1)= n ^ 2 + n; 我会说它与n ^ 2具有相同的增长顺序; 所以我会说
n(n + 1)= THETA(n ^ 2)
但我的问题是,说:这也是正确的:
n(n + 1)= ORDER(n ^ 2)
请帮助,因为这让我很困惑.谢谢.
感谢你们!!
只是为了确保我理解正确,这些都是真的:
n ^ 2 + n = ORDER(2000n ^ 2)
n ^ 2 + n = THETA(2000n ^ 2)
n ^ 2 + n = OMEGA(2000n ^ 2)
2000n ^ 2 = ORDER(n ^ 2 + n)
2000n ^ 2 = THETA(n ^ 2 + n)
2000n ^ 2 = OMEGA(n ^ 2 + n)
因此,如果f = THETA(g),那么f = ORDER(g)和f = OMEGA(g)也是如此.