2007/10/21

Incompatibility

昨天企圖從隨機客的 little-o 定義推到 CLRS 的定義(反向是 trivial),發現怎麼湊都不對,最後造了一組反例:

則 f(n) = O(g(n)) 且 f(n) \neq \Omega(g(n)),依隨機客的定義就有 f(n) = o(g(n))。但考慮 CLRS 的定義(也就是常見的定義),若取 c = 1/2,則 f(n) > c g(n) infinitely often,不可能在哪個 n_0 之後恆有 f(n) < c g(n)。所以隨機客的定義條件是比較弱的。寫信給隨機客,但他似乎不打算回應… 剛剛想用隨機客的定義反證作業第一題逼隨機客出面,但試了之後發現好像沒辦法,因為 n^2 太正常了(compared with the g(n) above)。

--
真煩,不管了。


現在用 Weijin 的帳號貼到隨機板上了。這樣應該很難裝作沒看到?XD

 作者  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

隨機客終於回了!

→ hil:有趣的例子! ;)                                           推 10/21 23:51
→ hil:好像變得有點像哲學問題, 就是這種狀況要不要當作little-o?  推 10/21 23:52
→ hil:為了不要搞混大家, 我們還是維持原來課堂上的定義.          推 10/21 23:53
→ hil:畢竟這樣的定義對於「一般」的演算法時間複雜度的函數是OK的 推 10/21 23:53
→ hil:「隨機客」明年再改成課本那樣好了..                       推 10/21 23:54
→ hil:Good job!! (or nice boat? ;)                             推 10/21 23:55

--
所以真的沒收到我的信嗎…?

Labels: