如何用 θ 求 (n^3)/1000 - 100n^2 - 100n + 3 并证明它？

Question

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

用 θ 符号表示函数 (n^3)/1000 - 100n^2 - 100n + 3

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

但是当我看到这篇文章时 -

如何用 θ 求 n^3/1000−100n^2−100n+3 并证明它？

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

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

Now you have a positive bound on C1

。

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

Answer 1

要系统地解决这个问题，最简单的方法是使用 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)

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

Answer 2

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

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