根据大O符号的定义,f(n)=O(g(n))等价于存在一个正常数C,使得对于充分大的n,有f(n)<=Cg(n)。因此,我们需要找到一个正常数C,使得f(n)<=Cg(n),即:

log4(n)<=Cnlogn

移项得:

logn/log4<=Cn

再移项得:

logn/(nlogn)<=C

因此,我们可以取C=1,因为当n足够大时,有logn/(nlogn)<=1,因此f(n)=O(g(n))。

fn= log4gn= nlogn满足fn=gn。

原文地址: https://www.cveoy.top/t/topic/fjkM 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录