已知函数f(n)∈O(g(n)),可以推出2^f(n)∈O(2^g(n))也成立吗

polyrandom · #1 (**permalink**) 2007-05-09

不知道哪个白痴说要写10个字

zero · #2 (**permalink**) 2007-05-09

不可以
$f(n)=3n^2, g(n)=n^2, 3n^2 \in O(n^2)$
$\exist n_0, \forall n > n_0, \exist c , 2^{f(n)} = 2^{3n^2} > c2^{n^2},$

关键在于
$f(n) \in O(g(n)) \Rightarrow f(n) < cg(n)$
but if $2^{f(n)} \in O(2^{g(n)})$ , we must have $f(n) < c_0 + g(n)$ ,

主题工具
显示可打印版本邮寄本页给好友
显示模式
平板模式切换到混合模式切换到树形模式