algorithm - Big Theta Notation - 简化

Question

我已经使用主定理来解决递推关系。我已经把它降低到 Θ(3n²-9n)。这是否等于 Θ(n²)？我有另一个循环，其解决方案是 Θ(2n³ - 100²)。在 BigTheta 表示法中，您总是只使用最大项吗？那么我的第二个是Θ(n³)？在第二种情况下，100n² 似乎更重要。如果我丢弃它会有关系吗？

有什么建议吗？

Answer 1

是的。你的假设是正确的。第一个是Θ(n²)，第二个是Θ(n³)。当您使用 Θ 表示法时，您只需要最大项。

如果您的第二次重复出现，请考虑 n = 1000，然后 n³ = 1000000000。其中 100n² 只是 100000000。随着 n 值的增加，n³ 变得比 100n² 越来越重要。

出于理论目的，您无需考虑常量，无论它有多大。但实际应用可能更喜欢具有小常数的算法，即使复杂度很高。例如，使用复杂度为 0.01n ³ 的算法可能比使用复杂度为 10000n² 的算法更好如果 n 的值不是很大。