我今天才知道这个关系不成立，因为 log 改变了函数的行为。但这是真的吗？举个例子就好了。
如果 f(n) = ϴ(g(n))，log(f(n)) = ϴ(log(g(n)) 成立吗？
如有任何帮助，我们将不胜感激。预先感谢。
现在评论已经表明这个问题是关于渐近极限而不是关于算法复杂度......
您可以使用 L'Hôpital 规则（信息存在于任何微分学基础文本中）以及
ln(x)1/xf(n)/g(n)log(f(n))/log(g(n))请注意，这与算法复杂性几乎没有关系。
如果我们将“O(g)中的f”表示为“存在一个正实数M和实数N，使得|f(n)|≤Mg(n)” 对于所有 n>N”，如果 g(n)=1，则索赔可能会失败。
反例：令f(n)=a且g(n)=1，其中a是对数的底数。 那么 f(n) 就在 O(g(n)) 中，因为
a=|f(n)|≤ag(n)=a
对于所有n>0。然而，不存在（正）实数 M 和实数 N 使得
1=|log(f(n))|≤Mlog(g(n))=0
对于所有 n>N，因此 log(f(n)) 在 O(log(g(n))) 中不是。
但是，该主张适用于更一般的情况 g(n):
声明： 如果对于所有 n>K log(g(n))>0，对于所有 n>L f(n)>0，且 f(n) 在O(g(n))，则 log(f(n)) 位于 O(log(g(n))。
证明：由于f(n)在O(g(n))中，存在正实数M和实数N使得
|f(n)|≤Mg(n)
对于所有n>N。现在对两边应用log，注意这个函数是单调的，得到
|log(f(n))|=log(|f(n)|)≤log(Mg(n))=log(M)+log(g(n))
对于所有 n>max(N, L)。 由于 log(g(n))>0 对于 n>K，存在 B>0 使得
log(M)≤博客(g(n))=log((g(n))^B)
对于n>K。因此，
|log(f(n))|≤log(M)+log(g(n))≤博客(g(n))+log(g(n))=(B+1)g(n)
对于所有 n> max(N,L,K)，因此 log(f(n)) 位于 O(log(g(n)))。