math - 计算 Omega 以提高算法效率

Question

我无法理解计算算法的效率。这是我的问题之一。有人可以帮助解释使用什么方法来解决这个问题吗？这本书非常混乱，并没有花很多时间在这上面。

找到函数 n^3 和 3n^3 - 2n2 + 2 之间的适当 Ω 关系并找到常数 c 和 n0

我知道 n^3 和 3n^3 之间没有太大区别，但我不确定如何找到常数 c 和 n0；

Answer 1

函数 n ³和 3n ³ - 2n ² + 2 实际上是彼此的 Θ，这意味着它们以相同的速率增长。应该可以对每个函数进行下限。

在第一个方向，请注意

3n ³ - 2n ² + 2

≥ 3n ³ - 2n ²

≥ 3n ³ - 2n ³

= n ³

因此，如果你选择 c = 1 和 n ₀ = 0，那么对于任何 n ≥ n ₀，我们得到 3n ³ - 2n ² + 2 ≥ cn ³，所以 3n ³ - 2n ² + 2 = Ω(n ³ )

我将把相反的方向作为众所周知的练习留给读者。:-)

希望这可以帮助！