作者micklin (mick doohan)
看板CSSE
标题Re: [问题] 几题BigO证明还有观念疑问
时间Tue Oct 5 19:51:08 2010
※ 引述《Lizstlin (Lizst)》之铭言：
: (因为是第一次在这边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 是推敲出来的 ~"~
n!可以用 Stirling's approximation 来证,
(
http://zh.wikipedia.org/zh-tw/%E6%96%AF%E7%89%B9%E9%9D%88%E5%85%AC%E5%BC%8F)
根号里的值大於零, 後面是n^n.
c在过程中不是用假设的,
那句 「s.t f(n)<=c*g(n)」的意思是「使得 f(n)<=c*g(n)成立」
所以只要能找到一个c可以让f(n)<=c*g(n)就可以了, 不是要算出c的最小值什麽的.
用你的证明来看, 先证明 n! <=c*(n^n) 是蛮奇怪的....
如果题目是 n!=O(?), 那你不就从n^n^n^n^n开始试到n^n?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 120.124.164.176
1F：推 Lizstlin:那麽请问除了 Stirling's approximation 10/06 23:30
2F：→ Lizstlin:还有其他方法吗? 因为那个我还没学到~"~ 谢谢^^ 10/06 23:30
3F：→ manlike:所以他用计算的方式找到n0和c 错了吗? = =" 10/07 01:19
4F：→ manlike:第一题考试写根据Stirling's Approximation 得f(n)=O(n^2) 10/07 01:22
5F：→ manlike:更正f(n!)=O(n^2), 会得分吗? 杀鸡用牛刀... = =" 10/07 01:23
6F：→ manlike:喔不对~ n! = O(n^2) ...= ="" 10/07 01:25
7F：→ Lizstlin:我今天去问助教, 他说OK 10/07 16:09
8F：→ Lizstlin:另外就是 n0 跟 c 只要 >=1 基本上都行 10/07 16:10
9F：→ Lizstlin:不过不是直接设, 是推算出来就是了 ^^" 10/07 16:11
10F：→ Lizstlin:感谢板上大大们不吝指教 ^^ 10/07 16:12