[轉錄][演算] 小o的證明
作者 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
→
10/21 21:19,
10/21 21:19
→
10/21 21:24,
10/21 21:24
→
10/21 21:25,
10/21 21:25
→
10/21 23:51,
10/21 23:51
→
10/21 23:52,
10/21 23:52
→
10/21 23:53,
10/21 23:53
→
10/21 23:53,
10/21 23:53
→
10/21 23:54,
10/21 23:54
→
10/21 23:55,
10/21 23:55
→
10/22 01:52,
10/22 01:52
→
10/22 01:53,
10/22 01:53
→
10/22 11:29,
10/22 11:29
→
10/22 11:30,
10/22 11:30
→
10/22 11:31,
10/22 11:31
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.114.199.106
→
11/01 13:43, , 1F
11/01 13:43, 1F