[理工] 複雜度計算

看板Grad-ProbAsk作者 (O_O)時間7年前 (2017/02/10 16:27), 7年前編輯推噓4(4推 0噓 11→)
留言15則, 5人參與, 最新討論串1/1
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
→
02/10 16:33, , 1F
把sqrt(n)直接忽略不知道可不可以？
02/10 16:33, 1F
感覺不太嚴謹@@，我朋友提點我「可以用夾擠，介於3n/2, n/2之間」，但是我慧根不足 無法領悟... ※ 編輯: ssssIssss (140.112.25.99), 02/10/2017 16:40:54
推
02/10 16:39, , 2F
忽略然後用substitution證~
02/10 16:39, 2F
推
02/10 16:42, , 3F
同上
02/10 16:42, 3F
推
02/10 17:03, , 4F
同上
02/10 17:03, 4F
是直接忽略sqrt(n)然後直接做嗎？ ※ 編輯: ssssIssss (140.112.25.99), 02/10/2017 17:12:49
→
02/10 17:27, , 5F
忽略sqrt(n)，解釋一下為什麼可以忽略，然後猜一個答案
02/10 17:27, 5F
→
02/10 17:27, , 6F
大概是O(n)吧！然後去證明他
02/10 17:27, 6F
Ok! 感恩！大家明天加油！ ※ 編輯: ssssIssss (140.112.25.99), 02/10/2017 17:38:39
推
02/10 17:46, , 7F
當n大於等於9時，sqrt(n)<=n/3
02/10 17:46, 7F
→
02/10 17:47, , 8F
變T(n)=T(n/2+n/3) + n 然後用substitution method
02/10 17:47, 8F
→
02/10 17:50, , 9F
突然發現我對substitution不熟，我寫一下我的過程，讓
02/10 17:50, 9F
→
02/10 17:50, , 10F
大家幫我看看有沒有不完整的地方：
02/10 17:50, 10F
→
02/10 17:50, , 11F
就用G大的式子好了
02/10 17:50, 11F
→
02/10 17:51, , 12F
T(n)=T(5n/6)+n，假設T(m) <= cm, for all m < n
02/10 17:51, 12F
→
02/10 17:52, , 13F
=> T(n) <= (5/6)cn+n = ((5/6)c+1)n
02/10 17:52, 13F
→
02/10 17:54, , 14F
當c >= 6時，((5/6)c+1)n <= ((5/6)c+(1/6)c)n = cn
02/10 17:54, 14F
→
02/10 17:55, , 15F
得證
02/10 17:55, 15F
Yep ※ 編輯: ssssIssss (223.136.188.70), 02/11/2017 07:26:21
‣ 更多 ssssIssss 的文章
文章代碼(AID): #1OdNbx87 (Grad-ProbAsk)