作者Lizstlin (Lizst)
看板TransCSI
标题[请益] BigO证明观念以及几题证明
时间Tue Oct 5 01:05:22 2010
因为老师上课没讲什麽证明范例, 书上也写得少
自己找题目写遇到不少瓶颈, 我知道基本观念是
f(n) = O(n) iff there exist positive constants c and n0 s.t
f(n) <= c*g(n) for all n which n >= n0
那个c 在证明过程中可以随便假设吗?
因为总觉得要有一定范围才可以, 像下面的证明我设1就不知道怎麽继续下去
证明题如下:
show that n! = O(n^n)
show that n^(2^n) + 6*2(^n) = θ(2^(2^n))
show that n^2 * logn = θ(n^2) is incorrect
大致上就是这些了, 希望有大大不吝指教, 谢谢 (拜)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.202.53
1F：推 Asbarla:C是时间常数 不要为负 10/08 00:59
2F：推 Asbarla:第三个问题用矛盾证法 假设他是对的 就会存在一组C和N0 10/08 01:01
3F：推 Asbarla:带进去算到最後会发现N会<=(>=)C*xx 很明显会矛盾 就得证 10/08 01:08
4F：推 Asbarla:bigO 要取C我会取最高项系数加1就是了 同理omega是减1 10/08 01:14