0

我无法解决证明问题。其中 t(n) <= c(5n + 9nlogn^5),c 是一个常数。一般来说,Big Omega 与 Big O 相反,因为它是最好的情况,并寻找下限。所以存在 ac 和 n0 使得 n >= n0。但我不确定如何将其应用于证明以及如何操纵方程中的常数以找到 c 和 n0 并证明 t(n) 是Omega(5n + 9nlogn^5)

t(n) = n + n logn^2 is/= Omega(5n + 9nlogn^5)

谁能提供一些有关如何解决此类问题的见解?

4

1 回答 1

0

According to definition of Big-Omega, f(n) is Ω( g(n) ) mathematically means
0 ≤ C⋅g(n) ≤ f(n), for any constant C > 0 and n > n'
Here,
f(n) = n + n⋅log(n²) = n + 2⋅n⋅log(n) and
g(n) = 5n + 9n⋅log(n⁵) = 5n + 45n⋅log(n).

and we want to prove 0 ≤ C * g(n) ≤ f(n).

Now, taking C = 1/45,

(1/45)⋅(5n + 45n*log(n)) = (n/9 + n⋅logn) <= (n + 2n⋅logn)

Hence, 0 ≤ (1/45)⋅g(n) ≤ f(n)f(n) is Ω(g(n)) for C = 1/45 and n > 0.

于 2013-02-03T13:54:09.580 回答