algorithm - 如何找到给定关系的时间复杂度？

Question

给定函数 f 和 g 使得 f(n)=O(g(n)) .

是f(n)∗log₂(f(n)c)=O(g(n)∗log₂(g(n) )) ？

(这里 c 是一些正常数。)

你应该假设 f 和 g 是非递减的并且总是大于 1。

谁能帮我解决这个问题？

预先感谢您的解释。

Answer 1

知道f(n) = O(g(n))知道 f(n) <= Dg(n)对于一些正常数 D每当n足够大。换句话说，存在一些 N使得先前的不平等适用于所有n > N .

现在，对于 n > N , 我们有

f(n)lg(f(n)c) <= Dg(n)lg(Dg(n)c)               ; lg is an increasing function
              <= Dg(n)lg(g(n)) + Dg(n)lg(cD)   ; lg(xy)=lg(x)+lg(y)

现在取一个正常数E这样 lg(cD)D <= Elg(g(1)) .我们得到

              <= Dg(n)lg(g(n)) + Eg(n)lg(g(1))
              <= Dg(n)lg(g(n)) + Eg(n)lg(g(n)) ; g is non-decreasing
              <= (D + E)g(n)lg(g(n))
               = O(g(n)lg(g(n)))               ; by definition