我正在阅读 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
。
这说明什么?请帮助我理解这里的概念。
如果“n”较大,则 1000n^3 相对比其他 n^2 或 n 部分变得更大。
所以 ans 应该是 theta(n^3)