作者Lizstlin (Lizst)
看板CSSE
标题[问题] 几题BigO证明还有观念疑问
时间Tue Oct 5 01:24:12 2010
(因为是第一次在这边PO文, 不大确定能否问这样的问题, 如果不行就麻烦版主删了,
不好意思喔 ^^")
因为老师上课没讲什麽证明范例, 书上也写得少
自己找题目写遇到不少瓶颈, 我知道基本观念是
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
希望有大大不吝指教, 大致上提点我该如何下手, 谢谢 (拜)
如果不懂我再来问各位大大 ^^"
方才自己试了一下第一题, 不知道这样对不对?
n! <= c*(n^n)
移项得 c* n[n^(n-1) - (n-1)!] >= 0
由 [n^(n-1) - (n-1)!] 得 n >= 1, 而 c >= 1
所以 n! = O(n^n) for all n which n>=1, and c>=1
这样的感觉还是很像c 还有 n0 是推敲出来的 ~"~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.202.53
1F：→ hilorrk:exist和for all不一样...你随便带一个进去当然不一定对 10/05 01:27
2F：→ hilorrk:也许你可以从"找出一个c"符合条件的方向去想 10/05 01:28
3F：→ hilorrk:像是第一题 1*2*...*n和n*n*...*n 你找不找的到c? 10/05 01:29
4F：推 nowar100:是拿来证明到最後，我们可以得到结论存在这个c 10/05 07:27
5F：→ nowar100:而不是先假设一个c去证吧 10/05 07:27
6F：→ Lizstlin:那麽, 可以提示(或是从中解一题当范例)讲解给我吗? 谢谢 10/05 10:12
7F：→ Lizstlin:比方第一题, 我试过左右除以n, 但是c 还是无法独立求出 10/05 10:29
※ 编辑: Lizstlin 来自: 140.115.189.100 (10/05 11:12)
※ 编辑: Lizstlin 来自: 140.115.189.100 (10/05 11:19)
8F：推 cooper6334:不是就随便凑一个c跟n0，只要有合就ok了吗? 10/07 23:55