请问O(O(f(n))) = O(f(n))的证明格式怎么写？我能想象，

精选知识

把那个常数系数带进证明中即可：

令 g(n) = O(f(n)),则 g(n) <= c1 f(n),当 n 足够大.

h(n) = O(g(n)) = O(O(f(n))),则 h(n) <= c2 g(n),当 n 足够大.

所以：h(n) <= c2 c1 f(n),当 n 足够大.

所以：h(n) = O(f(n))

其他类似问题

问题1：请问如何证明,如果f(n) = O(g(n)) 和g(n) = o(h(n)) 同时成立,推出f(n) = o(h(n))上面的三个O中,第一个是bigO,后两个是小o[数学科目]

f(n)/g(n)->C

g(n)/h(n)->0

那么

f(n)/g(n)*g(n)/h(n)->C*0=0

即

f(n)=o(h(n))

问题2：big O中,f(n)=O(g(n))如何证明 n>1即可?我们知道f(n)=O(g(n)) 是 f(n)= n0,n0>0,c > 0.但是,要如何证明 f(n) 0[数学科目]

g(n)都是正的吗

取C'=max(c,f(1)/g(1),f(2)/g(2),.f(n0)/g(n0)) 即可

问题3：请举例说明存在函数f(n),有f(n)≠O(n)且f(n)≠Ω(n),一道算法题[数学科目]

题设本身错误!

假设 f(n) ≠ O(n) 成立.

那么,?C > 0 ,? K > 0 ,当 n > K 时,有 f(n) > C * n .(定义)

所以 任取 C > 0 ,取 K' = K ,当 n > K' 时,有 f(n) > C * n

根据Ω定义.,可知 f(n) ∈Ω(n) 与 题设的第二条件矛盾!

所以题设本身错误!

问题4：如何证明如果 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))

问题5：算法分析与设计 证明如下定理如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n))1、试证明下面的定理：(1) 如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n))(2) 如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)*g([数学科目]

（1）不失一般性,假设f(n)>=g(n) ,则f(n)+g(n)