[轉錄][演算] 小o的證明

[ajnightmare (阿華田)]

 作者  jimbedb (XD)                                                 看板  hil 
 標題  [問題] little-o 的定義與課本不相容？                                   
 時間  Sun Oct 21 20:57:20 2007                                               
───────────────────────────────────────

老師在 slide 1 p.94 對 f(n) = o(g(n)) 的定義是

    f(n) = O(g(n))    and    f(n) \neq \Omega(g(n))，

而課本在 p.48 的定義（以及查得到的所有其他定義）是

    for any c > 0, there exists n_0 > 0 s.t. f(n) < c g(n) when n > n_0。

第一個定義的條件是比較弱的。若我們令

    f(n) = n，

    g(n) = n      if n is odd
         = 2^n    if n is even，

那麼 f(n) = O(g(n)) 而且 f(n) \neq \Omega(g(n))，所以 f(n) = o(g(n))。
但在第二個定義下，若取 c = 1/2，f(n) 會在奇數點上大於 g(n)/2，而不可能
在某個 n_0 之後使 f(n) < c g(n) 恆成立，因此 f(n) \neq o(g(n))。

所以第一個定義是不是不夠充分呢？

※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.249.77
→ xxxholic:f(n) = n g(n)/2 = 2^(n-1)(even)  n > 2^(n-1) ??
→ jimbedb:是奇數點，謝謝指正~
→ xxxholic:我ㄧ瞬間以為我看錯了orz
→ hil:有趣的例子! ;)
→ hil:好像變得有點像哲學問題, 就是這種狀況要不要當作little-o?
→ hil:為了不要搞混大家, 我們還是維持原來課堂上的定義.
→ hil:畢竟這樣的定義對於「一般」的演算法時間複雜度的函數是OK的
→ hil:「隨機客」明年再改成課本那樣好了..
→ hil:Good job!! (or nice boat? ;)
→ spookySue:nice boat 大概不是這樣用的XDDD
→ spookySue:不過在作業中 我可以不要考慮這種極端情形嗎....|||
→ hil:樓上跟VampireGirl的ID都挺嚇人..
→ hil:「隨機客」是陸軍, 難怪搞不懂船隻
→ hil:作業還是以課堂上的定義為準.
--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 58.114.199.106
→ ajnightmare:這樣日子就難過了