如果 f(n) = O(g(n))，则 log(f(n)) = O(log(g(n))？
If f(n) = O(g(n)), is log(f(n)) = O(log(g(n))?
我今天才知道这个关系不成立，因为日志改变了函数的行为。但这是真的吗？一个例子会很好。
如果 f(n) = ϴ(g(n))，log(f(n)) = ϴ(log(g(n)) 是否成立？
感谢任何帮助。提前致谢。
既然评论已经表明这个问题是关于渐近极限而不是关于算法复杂性的......
您可以使用 L'Hôpital 规则（信息在任何有关微积分的基础文本中）和 ln(x)（自然对数）的导数是 1/x 的事实来证明渐近f(n)/g(n) 的极限等于 log(f(n))/log(g(n)).
的渐近极限
请注意，这与算法复杂性几乎没有关系。
之前的回答不正确。例如，
令f(n)=a和g(n)=1，其中a是对数的底数。那么f(n)在O(g(n))。事实上，f(n)<=cg(n) 代表所有 n>0，其中 c=a。但是，log(f(n))=1 和 log(g(n))=0。现在 1 不在 O(0) 中。事实上，不存在常量 C 和 N 这样 1=log(f(n))<=Clog(g(n))=0 对所有 n>N.
但是，假设log(g(n))>0。由于 f(n) 在 O(g(n)) 中，我们有常量 A 和 N 使得所有 n>=N 的 f(n)<=Ag(n)。现在将 log 应用到两边，注意这个函数是单调的以获得 log(f(n))<=log(Ag(n))=log(A)+log(g(n))。由于 log(g(n))>0 存在 B 使得 log((g(n))^B)=Blog(g(n))>=log(A)。因此，对于所有 n>= N，log(f(n))<=log(A)+log(g(n))<=Blog(g(n))+log(g(n))=(B+1)(g(n))。因此，f(n) 在 O(g(n)).
中
我今天才知道这个关系不成立，因为日志改变了函数的行为。但这是真的吗？一个例子会很好。
如果 f(n) = ϴ(g(n))，log(f(n)) = ϴ(log(g(n)) 是否成立？
感谢任何帮助。提前致谢。
既然评论已经表明这个问题是关于渐近极限而不是关于算法复杂性的......
您可以使用 L'Hôpital 规则（信息在任何有关微积分的基础文本中）和 ln(x)（自然对数）的导数是 1/x 的事实来证明渐近f(n)/g(n) 的极限等于 log(f(n))/log(g(n)).
请注意，这与算法复杂性几乎没有关系。
之前的回答不正确。例如，
令f(n)=a和g(n)=1，其中a是对数的底数。那么f(n)在O(g(n))。事实上，f(n)<=cg(n) 代表所有 n>0，其中 c=a。但是，log(f(n))=1 和 log(g(n))=0。现在 1 不在 O(0) 中。事实上，不存在常量 C 和 N 这样 1=log(f(n))<=Clog(g(n))=0 对所有 n>N.
但是，假设log(g(n))>0。由于 f(n) 在 O(g(n)) 中，我们有常量 A 和 N 使得所有 n>=N 的 f(n)<=Ag(n)。现在将 log 应用到两边，注意这个函数是单调的以获得 log(f(n))<=log(Ag(n))=log(A)+log(g(n))。由于 log(g(n))>0 存在 B 使得 log((g(n))^B)=Blog(g(n))>=log(A)。因此，对于所有 n>= N，log(f(n))<=log(A)+log(g(n))<=Blog(g(n))+log(g(n))=(B+1)(g(n))。因此，f(n) 在 O(g(n)).