作者ajnightmare (阿华田)
看板NTUBIME100HW
标题[转录][演算] 小o的证明
时间Sat Nov 1 13:43:07 2008
作者 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
1F：→ xxxholic:f(n) = n g(n)/2 = 2^(n-1)(even) n > 2^(n-1) ??推 10/21 21:19
2F：→ jimbedb:是奇数点，谢谢指正~推 10/21 21:24
3F：→ xxxholic:我ㄧ瞬间以为我看错了orz推 10/21 21:25
4F：→ hil:有趣的例子! ;)推 10/21 23:51
5F：→ hil:好像变得有点像哲学问题, 就是这种状况要不要当作little-o?推 10/21 23:52
6F：→ hil:为了不要搞混大家, 我们还是维持原来课堂上的定义.推 10/21 23:53
7F：→ hil:毕竟这样的定义对於「一般」的演算法时间复杂度的函数是OK的推 10/21 23:53
8F：→ hil:「随机客」明年再改成课本那样好了..推 10/21 23:54
9F：→ hil:Good job!! (or nice boat? ;)推 10/21 23:55
10F：→ spookySue:nice boat 大概不是这样用的XDDD推 10/22 01:52
11F：→ spookySue:不过在作业中 我可以不要考虑这种极端情形吗....|||推 10/22 01:53
12F：→ hil:楼上跟VampireGirl的ID都挺吓人..推 10/22 11:29
13F：→ hil:「随机客」是陆军, 难怪搞不懂船只推 10/22 11:30
14F：→ hil:作业还是以课堂上的定义为准.推 10/22 11:31
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 58.114.199.106
15F：→ ajnightmare:这样日子就难过了 11/01 13:43