这个语句是否为false？我在这个网站上找不到这个问题的答案(只有大O)。
从定义我可以假设:log(C1g(n)) ≤ log(f(n)) ≤ log(C2g(n))
解出右侧:log(f(n)) ≤ log(C2g(n)) ≤ log(C2) + log(g(n))，因为log(g(n))>1，所以有C2log(g(n)) ≥ log(C2 ) => log(f(n)) ≤ C2log(g(n)) + log(g(n)) ≤ (C2+1)log(g(n))。
，但我找不到一个常数在左边:log(f(n)) ≥ log(C1g(n)) ≥ log(C1) + log(g(n)) ≥ log(g(n))让我们说C3log(g(n) < log(C1) C3 < log(C1)/log(g(n))-有一个解决方案吗?
意味着我不能证明log(f(n)) = Ω(log(g(n)))。如果可以的话，请把完整的证明给我看看。
根据定义:
c1*g(n) <= f(n) <= c2 g(n), for n > n0
当函数为正且log是递增函数时，我们可以得到:
log(c1*g(n)) <= log(f(n)) <= log(c2*g(n)), for n > n0
=> log(c1) + log(g(n)) <= log(f(n)) <= log(c2) + log(g(n)), for n > n0
现在，作为log(c1) + log(g(n)) <= log(f(n))，如果c1 >= 1，我们可以得出结论:
log(g(n)) <= log(f(n))
因此证明是完整的(同理对于log(f(n)) <= c2 * c1* log(g(n))如果c2 >= 1)。
如果c1 < 1(因此，log(c1) < 0)，我们需要找到一个常数c3 > 0，如下所示:
c3 * log(g(n)) < log(c1) + log(g(n))
-log(c1) < (1-c3) log(g(n))
=> -log(c1)/(1-c3) < log(g(n))
现在，作为g(n) >= 2对应每个n，如果我们有以下内容:
-log(c1)/(1-c3) < log(2) = 1
我们将满足Omega的定义。因此，c3的以下值对于定义是有效的:
-log(c1)/(1-c3) < 1
=> -log(c1) < 1- c3 => c3 < 1 + log(c1)
同样，如果log(c1) < -1，我们需要找到一个m0，使得g(n) > k对于每个n > m0和-log(c1)/(1-c3) < k至少有一个有效解，即c3 < 1 + log(c1)/k。换句话说，我们需要找到m0和k > 0，以便g(n) > k和log(c1)/k > -1。前者的意思是:
log(c1) > -k => c1 > 2^(-k)
语句确实是正确的。首先，我们假设f(n)和g(n)都是递增函数，随着n的增大而趋于无穷。那么根据位的定义，存在常数a和b，使得
a*g(n)<=f(n)<=b*g(n)
两边取对数得到
-log a+log g(n)<=log f(n)<=log g(n)+log b
为了不失去一般性，我们假设a<1、b>1和n足够大，使得g(n)>1。因此，我们得到以下不等式:
log g(n)<=log f(n)<=(1+log b)log g(n)
说明log f(n)是log g(n)的大θ