【两道关于函数的增长的证明题1.证明：f(n)=n^100,-查字典问答网

来自黄德中的问题

　　【两道关于函数的增长的证明题1.证明：f(n)=n^100,对g(n)=2^n是O(g)的,但g不是O(f)的.2.证明：对于f(n)=lg(n^3)和g(n)=log5(6n),f于g有相同的阶】

　　两道关于函数的增长的证明题

　　1.证明：f(n)=n^100,对g(n)=2^n是O(g)的,但g不是O(f)的.

　　2.证明：对于f(n)=lg(n^3)和g(n)=log5(6n),f于g有相同的阶

1回答

2020-04-12 00:04

我要回答

请先登录

姜宏

　　1.只要证明f(n)/g(n)趋于零,当n趋于无穷的时候.使用离散的罗比达法则,有

　　lim（f(n)/g(n))

　　=lim((100*n^99)/(2^n*ln2))

　　=lim((100!)/(2^n*(ln2)^100))

　　=0(n趋于无穷时),

　　反过来,显然g不是0（f）的

　　2.同1的思路,只证lim（f(n)/g(n))

　　=lim【lg(n^3)/（lg(6n)/lg5）】,

　　=lim【lg5*（lg(n^3)/lg（6n））】,

　　=lg5*lim【lg(n^3)/lg（6n）】

　　=lg5*lim【（3/x）/（1/x）】

　　=lg5*3(n趋于无穷时),

　　则f和g同阶

2020-04-12 00:09:23