[理工] 演算法 求時間複雜度

看板Grad-ProbAsk作者 (woody)時間12年前 (2013/11/09 16:58), 編輯推噓6(6推 0噓 17→)
留言23則, 6人參與, 最新討論串1/2 (看更多)
如連結 http://i.imgur.com/1MYHGxt.jpg
綠色字是題目 要求時間複雜度 紫色是我的算法 算到最後 請問 1/(i^2)的級數有公式嗎@@? 謝謝各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.240.46
→
11/09 18:57, , 1F
調和數列
11/09 18:57, 1F
推
11/09 19:58, , 2F
我是用Master Method看耶，a=2,b=2,f(n)=n/(logn)^2
11/09 19:58, 2F
→
11/09 20:00, , 3F
所以n^log_ab=n，f(n)是1/(logn)^2*n
11/09 20:00, 3F
→
11/09 20:02, , 4F
符合case1的情況所以T(n)=θ(n)這樣？
11/09 20:02, 4F
→
11/09 20:02, , 5F
這不能用master看 也不是調合數列 應該是O(n)
11/09 20:02, 5F
→
11/09 20:04, , 6F
可以請教一下為何不能用master看嘛？
11/09 20:04, 6F
→
11/09 20:06, , 7F
用master如果f(n)=n/logn答案是O(n*log(logn))喔非O(n)
11/09 20:06, 7F
推
11/09 20:09, , 8F
此題解法是1/i^2 積分上n下1就出來了(n-1)/n=O(1)
11/09 20:09, 8F
→
11/09 20:11, , 9F
跟調合證明很像 就像黎曼面積 1/i積分上n下1 =log(n)
11/09 20:11, 9F
→
11/09 20:13, , 10F
至於master的話 遇到有f(n)有n^loga_b會有問題(case2)
11/09 20:13, 10F
→
11/09 20:15, , 11F
所以能不要用其實盡量 像這類題的 用展開或遞迴樹比較好
11/09 20:15, 11F
推
11/09 20:16, , 12F
不好意思 題目給的f(n)不是是n/(logn)^2嘛？
11/09 20:16, 12F
→
11/09 20:16, , 13F
所以n在growth rate上應該比n/(logn)^2大不是嘛？
11/09 20:16, 13F
→
11/09 20:16, , 14F
小弟駑頓～麻煩大大再解釋一下！感激！
11/09 20:16, 14F
推
11/09 20:21, , 15F
謝謝大大解釋～我再研究看看
11/09 20:21, 15F
推
11/09 20:43, , 16F
有點偏的題目 考到證明的變型 一般都考O(nloglogn)那題
11/09 20:43, 16F
→
11/09 21:26, , 17F
人在外面@@ 我回家再解釋 如果有空的話XD
11/09 21:26, 17F
→
11/09 21:33, , 18F
那答案是什麼？ O(nlog(log^2n)) ?
11/09 21:33, 18F
→
11/09 21:48, , 19F
答案應該是O(n*loglogn)
11/09 21:48, 19F
→
11/09 23:03, , 20F
應該是O(n)吧 我解出來了@@ 另貼文了
11/09 23:03, 20F
推
11/10 09:00, , 21F
1/(i^2)就是Riemann zeta function帶入2的值..
11/10 09:00, 21F
→
11/10 09:00, , 22F
11/10 09:00, 22F
→
11/10 09:01, , 23F
當n為無窮大時，其值為pi^2 / 6 所以是一個常數..
11/10 09:01, 23F
‣ 更多 woody3724 的文章
文章代碼(AID): #1IVVbFmf (Grad-ProbAsk)
‣ 更多 woody3724 的文章
文章代碼(AID): #1IVVbFmf (Grad-ProbAsk)