Re: [理工] [演算法]遞迴求big oh

看板Grad-ProbAsk作者xling5216 (xling)時間13年前 (2013/03/13 12:51)推噓2(2推 0噓 3→)

留言5則, 4人參與討論串2/2 (看更多)

※ 引述《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

推

FRAXIS

03/13 21:39, , 1^F

03/13 21:39, 1^F

推

npes87184

03/13 22:28, , 2^F

03/13 22:28, 2^F

→

xling5216

03/13 23:13, , 3^F

03/13 23:13, 3^F