※ [本文轉錄自 yuhan210 信箱]
作者: yuhan210.bbs@ptt2.cc (yuhan210.bbs@ptt2.cc)
標題: Re: [damn]演算法
時間: Fri Oct 26 00:44:06 2007
作者: BNMAA (Trust Me) 看板: Matcha
標題: Re: [damn]演算法
時間: Fri Oct 26 00:42:24 2007
這個嘛
要澄清某件事
就是有位同學跟我說 課本上的theta(g(n))的定義是
f(n) = theta(g(n)) iff exist positive constant c, n0
s.t. f(n) = c*g(n) for all n >= n0
他沒說這麼詳細 不過大概是這個意思
我當時不太確定 但也懶得去證明它成立(但其實錯得很明顯 我在搞什麼~"~)
用了這東西跟好幾位同學講
但後來證一證發現!!! 它是錯的
其實是
f(n) = theta(g(n)) iff exist positive constants c1,c2,n0 (c1>=c2)
s.t. 0 <= c2*g(n) <= f(n) <= c1*g(n) for all n >= n0
這才是正確的
可以用老師定義theta(g(n))的方式(雙向big-Oh) 推出以上結論
被頭腦不清楚的我誤導的同學 希望你們有看到這一篇 (我不知道要po哪)
不如哪位善心人士幫我轉到b95功課板
晚安
祝你們的作業不必一改再改
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 61.230.69.115
※ scan33scan33:轉錄至看板 AcademicX 10/26 00:43
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.5.16