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

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/08/26 03:25:15

如何证明如果 lgf(n) = O(lgg(n))正确的那么 f(n) = O(g(n))也是正确的
f(n) = O(g(n))的定义是存在正实数c 使得有n1 当所有n>n1时，有f(n)

如果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))

big O中,f(n)=O(g(n))如何证明 n>1即可? 计算机算法设计题1、试证明下面的定理：(1) 如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g 算法分析与设计证明如下定理如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n) f(n)=n^2+o(n)的含义? (F/P,i,n)=(A/P,i,n)/(F/A,i,n)如何证明正确? 用所给的字母组合成正确的单词:o,i,n,m,r,g,n, 用字母组成正确的单词w n o d 用字母w o n d组成正确的单词一道高等代数的问题,设A与B都是n阶方阵.证明:如果AB = O,那么秩A + 秩B ≤ n . 设A与B都是n阶方阵.证明:如果AB=O,那么秩A+秩B≤n. a g k r o n a o 把这些英为字母,组合成正确的单词 n t m a o u n i组成正确的英语单词