【lgg】如何证明如果lgf(n)=O(lgg(n))正确的那么f(n)=O(g(n))也是正确的f...

【lgg】如何证明如果lgf(n)=O(lgg(n))正确的那么f(n)=O(g(n))也是正确的f...

【答案】 如果lgf(n)=O(lgg(n)),根据定义,当n足够大时有lgf(n)≤clg(g(n)),c为非零常数.所以f(n)≤g(n)^c,由于n足够大时g(n)趋于0,所以g(n)^c≤g(n),即f(n)≤g(n),所以f(n)=O(g(n)) 追问： 为什么当n足够大时g(n)趋于0？ 追答： f(n)=O(g(n))表示f(n)和g(n)是同阶无穷小，所以这个问题研究的就是f(n)和g(n)都是无穷小的情况，所以当n足够大时g(n)趋于0。 追问： f(n)=O(g(n))是结论，但是我在解答是不能用结论（同阶无穷小）去说，因为我要研究的是无穷小，所以g(n)要无穷小吧。这是用假设推条件吧 追答： 你说的也有道理，但我用的只是g(n)是无穷小这个事实，而没有用f(n)=O(g(n))，如果你认为g(n)不是无穷小，那lgg(n)就也不是无穷小，那么O(lgg(n))这个表示什么意思呢，所以我觉得题目应该写明前提条件，即f(n)和g(n)都是无穷小序列。 追问： 那么这道题就是没有写明条件，所以说明这个结论是错的了？ 其实这道题是要证明这个结论是正确或者不正确。并没有说明要证明这个结论是正确的。 追答： 你说的没错，如果f(n)=n^2，g(n)=n，它们都不是无穷小序列，而lgf(n)/lgg(n)=2lgn/lgn=2，所以满足lgf(n)=O(lgg(n))，而f(n)/g(n)=n说明f(n)/g(n)无界，所以得不出f(n)=O(g(n)) 查看全部追问追答

我明天再问问老师，叫他解释下这个问题

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息