大Omega表示法

Question

证明3n^2-25n=Ω(n^2)

For n ≥ n / 2           for n ≥ 0
    n – 25/3 ≥ 3n / (2 x 25)    for n ≥ 9
    3n^2 - 25n ≥ 9n^2 / 50      for n ≥ 9

    3n2 - 25n ≥ c·n2 for n ≥ n0 where c=9 / 50 and n0 = 9
Therefore, by definition
      3n2 - 25n = Ω(n2).

以上是3n^2-25n=Ω(n^2)的证明.

为什么使用n≥n/ 2

n-25/3≥3n /(2x25)是如何导出的？

Answer 1

我不知道为什么我们需要n >= n/2。我们需要的是n >= 0 => n*3 >=0，所以我们可以在两边把第一个不等式乘以3*n。

(1) n-25/3≥3n /(2x25)是一个简单的线性不等式。通过进行一些转换，我们可以得到：

(1) <=> (47/50)*n-25/3 >= 0 <=> (47/50)n >= 25/3 <=> n >= ( 25/3 )(50/47) <=> n >= 1250/141 <=> n >= 8+ 122/141

从上面我们得到，这个不等式适用于n，n，>= 9>8+ 122/141。这只是一个不等式，你可以用来证明这个大的omega表示法。希望我的回答有帮助。