algorithm - 运行时的渐近符号

Question

如果我有一个运行时间 T(n) = 5n^4/100000 + n^3/100 的算法，我知道我得到 Θ(n^4) 。

现在，如果我有类似 T(n) = (10n^2 + 20n^4 + 100n^3)/(n^4) 的结果，这是否会产生 Θ( n^3)?

我正在尝试消除低阶项以使用替换方法来证明这一点。

Answer 1

Big-Theta 意味着，增长既是big-O 也是big-Omega。

所以您问题中的第一个案例是 Θ(n^4) , 不是 Θ(n^3)自 5n^4/100000 + n^3/100属于O(n^4)而不是 O(n^3) .

第二种情况:

因此，它是 Θ(1) - 因为结果是 O(1)和 Ω(1) : 所有成员，20 除外(常量)在 n 时将限制为零正在增长。