如何证明如果 lgf(n) = O(lgg(n))正确的那么 f(n) = O(g(n))也是正确的
来源:学生作业帮 编辑:大师作文网作业帮 分类:数学作业 时间:2024/10/05 18:27:44
如何证明如果 lgf(n) = O(lgg(n))正确的那么 f(n) = O(g(n))也是正确的
f(n) = O(g(n))的定义 是存在正实数c 使得有n1 当所有n>n1时,有f(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))
再问: 为什么当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组成正确的英语单词