小弟是想跨考資工的初學者 對於某些演算法不慎明白
以下這題小弟困惑了許久 最後還是決定在板上問了
Solving the recurrence T(n)=2T(floor(sqrt(n)))+lgn
我照著洪傑的方法解
猜 T(n)=O(lgn*lglgn)
假設T(floor(sqrt(n)))<=c*lg(sqrt(n))*lglg(squt(n))成立
則
T(n)=2T(floor(sqrt(n)))+lgn
<=2*c*lg(sqrt(n))*lglg(sqrt(n))+lg2
=2*c*(1/2)*lgn*lg((1/2)*n)+lgn
=lgn(c*lglgn-c+1)
所以當c>=1時此式會成立
但是他再找boundary condition時
他取當 c=1 n0=1
T(n)<=lgn(clglgn-c+1)<=clgnlglgn 此式成立
但是我的問題是 當n0=1時
lglgn=lglg1=lg0
這樣這個式子不就沒有意義了嗎 為什麼還會成立?
然後我發現好像很多人在解substitution method時
都不會去證明boundary condition
是因為證明那些東西太瑣碎了
所以研究所考試的時候不會扣分嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.171.151.91
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1430972469.A.8C1.html
※ 編輯: forever3580 (118.171.151.91), 05/07/2015 16:50:12