算法分析——增长顺序问题

Question

我正在研究“大哦”、“大欧米茄”和“大西塔”的增长顺序。由于我无法为这些输入小符号，因此我将它们表示如下:

ORDER = 大哦
OMEGA = 大欧米茄
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) 与 n^2

我意识到 n(n+1) = n^2 + n;我会说它与 n^2 具有相同的增长顺序；所以我会说

n(n+1) = THETA(n^2)

但我的问题是，这样说是否也正确:

n(n+1) = 顺序(n^2)

请帮忙，因为这让我感到困惑。谢谢。

谢谢大家!!

只是为了确保我理解正确，这些都是真的吗:

n^2+n = ORDER(2000n^2)
n^2+n = THETA(2000n^2)
n^2+n = 欧米茄(2000n^2)

2000n^2 = 顺序(n^2+n)
2000n^2 = THETA(n^2+n)
2000n^2 = 欧米茄(n^2+n)

因此，如果 f = THETA(g)，则 f=ORDER(g) 和 f=OMEGA(g) 也成立。

Answer 1

是的，n(n+1) = Order(n^2) 是正确的。

如果 f = Theta(g) 则 f = Order(g) 和 g = Order(f) 都为真。