Re: [問題] 幾題BigO證明還有觀念疑問
看板CSSE (電腦科學及軟體工程)作者micklin (mick doohan)時間14年前 (2010/10/05 19:51)推噓1(1推 0噓 9→)留言10則, 2人參與討論串2/2 (看更多)
※ 引述《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
推
10/06 23:30, , 1F
10/06 23:30, 1F
→
10/06 23:30, , 2F
10/06 23:30, 2F
→
10/07 01:19, , 3F
10/07 01:19, 3F
→
10/07 01:22, , 4F
10/07 01:22, 4F
→
10/07 01:23, , 5F
10/07 01:23, 5F
→
10/07 01:25, , 6F
10/07 01:25, 6F
→
10/07 16:09, , 7F
10/07 16:09, 7F
→
10/07 16:10, , 8F
10/07 16:10, 8F
→
10/07 16:11, , 9F
10/07 16:11, 9F
→
10/07 16:12, , 10F
10/07 16:12, 10F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章