[理工] 複雜度計算

[ssssIssss (O_O)]

T(n) = T(n/2 + sqrt(n)) +n

想請教這題要怎麼求出複雜度m(_ _)m

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.99
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486715259.A.207.html
→ yupog2003: 把sqrt(n)直接忽略不知道可不可以？
感覺不太嚴謹@@，我朋友提點我「可以用夾擠，介於3n/2, n/2之間」，但是我慧根不足
無法領悟...
※ 編輯: ssssIssss (140.112.25.99), 02/10/2017 16:40:54
推 aa06697: 忽略然後用substitution證~
推 ken52011219: 同上
推 AllenPaul: 同上
是直接忽略sqrt(n)然後直接做嗎？
※ 編輯: ssssIssss (140.112.25.99), 02/10/2017 17:12:49
→ yupog2003: 忽略sqrt(n)，解釋一下為什麼可以忽略，然後猜一個答案
→ yupog2003: 大概是O(n)吧！然後去證明他
Ok! 感恩！大家明天加油！
※ 編輯: ssssIssss (140.112.25.99), 02/10/2017 17:38:39
推 Gabino: 當n大於等於9時，sqrt(n)<=n/3
→ Gabino: 變T(n)=T(n/2+n/3) + n 然後用substitution method
→ yupog2003: 突然發現我對substitution不熟，我寫一下我的過程，讓
→ yupog2003: 大家幫我看看有沒有不完整的地方：
→ yupog2003: 就用G大的式子好了
→ yupog2003: T(n)=T(5n/6)+n，假設T(m) <= cm, for all m < n
→ yupog2003: => T(n) <= (5/6)cn+n = ((5/6)c+1)n
→ yupog2003: 當c >= 6時，((5/6)c+1)n <= ((5/6)c+(1/6)c)n = cn
→ yupog2003: 得證
Yep
※ 編輯: ssssIssss (223.136.188.70), 02/11/2017 07:26:21