如何用 θ 求出 {n^3}{1000} - 100n^2 - 100n + 3 并证明它？

Question

我正在阅读 coreman 的《算法简介》，并发现了下面的练习：

Express the function {n^3}{1000} - 100n^2 - 100n + 3 in terms of the Θ notation 

我没有任何计算机科学背景，所以尝试使用这本书来学习算法。看看上面的方程，我认为答案是 O(n^3)。

但是当我看到这篇文章时 - 如何用 θ 求 n^3/1000−100n2−100n+3 并证明它？

上面帖子中的问题使用 f(n) 和 g(n) 以及常数 C1 和 C2 等进行了一些解释，我无法理解OP如何尝试使用一些方程来解决它。

另外，罗斯给出的答案，他提到它为

Now you have a positive bound on  C1

。这说明了什么。请帮助我理解这里的概念。

Answer 1

答案将是 θ(n3)。

要系统地解决这个问题，最简单的方法是使用 Big-O 和 θ 的七个规则，网址为 http://web.cs.wpi.edu/~guttman/cs2223/seven_rules.pdf。 将原表达式写成 e，重复应用规则 (2) 告诉我们 θ(e) = θ(最大(n^3/1000 - 100n^2 - 100n + 3))

将规则 (1) 应用于其中每一个，这将等于 θ(max(n^3, n^2, n, 1))。

现在我们可以应用规则（4）来查看 θ(1) < Θ(n) < Θ(n^2) < Θ(n^3):

所以 θ(max(n^3, n^2, n, 1)) = θ(n^3).

Answer 2

用 Theta 表示符号， 我们需要查看相对于较大输入大小增长最快的术语。

如果“n”较大，则 1000n^3 相对比其他 n^2 或 n 部分变得更大。

所以 ans 应该是 theta(n^3)