推 FRAXIS:如果B(n)可以忽略 那原題中的T(n/2)可以直接忽略嗎？ 03/13 21:39
推 npes87184:我覺得應該不可以忽略 T(n/2) 03/13 22:28
→ xling5216:我在解這題的時候想說是求BIG-O 所以忽略掉了 03/13 23:13
→ sting47:可是big-oh如果不tight的話，只要是填大於它的複雜度都對 03/14 01:57
→ sting47:啊@@ 填個O(n^n)也是對啊orz 03/14 01:57
※ 引述《npes87184 (Freyalolz)》之銘言：
: t(n)=t(n-1)+t(n/2)+n
: 我是猜是n平方，可是證不出來。
: 還是說他不是n^2?
: https://www.dropbox.com/s/509h0ct1queq6sy/IMAG0120.jpg
我又來了
以下是不負責解法
就是亂猜的XD
t(n) =t(n-1)+t(n/2)+n ---------------------------------------(1)
t(n-1)=t(n-2)+t((n-1)/2)+(n-1)--------------------------------(2)
(1)-(2)得
t(n) =2t(n-1)-t(n-2)+t(n/2)-t((n-1)/2)+1---------------------(3)
t(n-1)=2t(n-2)-t(n-3)+t((n-1)/2)-t((n-2)/2)+1-----------------(4)
(3)-(4)得
t(n)=3t(n-1)-3t(n-2)+t(n-3) + t(n/2)-2t((n-1)/2)+t((n-2)/2)-----(5)
￣￣￣￣￣￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣￣￣￣
另A(n)=3t(n-1)-3t(n-2)+t(n-3)
B(n)=t(n/2)-2t((n-1)/2)+t((n-2)/2)
則t(n)=A(n)+B(n)
而可以知道當ｎ夠大時A(n)遞回的速度一定會比B(n)慢
所以可以直接忽略B(n)
(這裡有點牽強我在猜是否可以A(n)和B(n)都解開，但基本上A(n)有三個１的根，而
B(n)經過轉換後也只有兩個１的根，基本上還是不會超越A(n))
最後解A(n)=(a*n^2+b*n+c) 其中a.b.c為未定係數
最後得到t(n)=Ｏ(n^2)
唬爛完畢....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.189.36