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

[woody3724 (woody)]

如連結

http://i.imgur.com/1MYHGxt.jpg

綠色字是題目  要求時間複雜度

紫色是我的算法

算到最後

請問 1/(i^2)的級數有公式嗎@@?

謝謝各位

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.240.46
→ ken1325:調和數列
推 DoubleFish:我是用Master Method看耶，a=2,b=2,f(n)=n/(logn)^2
→ DoubleFish:所以n^log_ab=n，f(n)是1/(logn)^2*n
→ DoubleFish:符合case1的情況所以T(n)=θ(n)這樣？
→ kiki86151:這不能用master看 也不是調合數列 應該是O(n)
→ DoubleFish:可以請教一下為何不能用master看嘛？
→ kiki86151:用master如果f(n)=n/logn答案是O(n*log(logn))喔非O(n)
推 kiki86151:此題解法是1/i^2 積分上n下1就出來了(n-1)/n=O(1)
→ kiki86151:跟調合證明很像 就像黎曼面積 1/i積分上n下1 =log(n)
→ kiki86151:至於master的話 遇到有f(n)有n^loga_b會有問題(case2)
→ kiki86151:所以能不要用其實盡量 像這類題的 用展開或遞迴樹比較好
推 DoubleFish:不好意思 題目給的f(n)不是是n/(logn)^2嘛？
→ DoubleFish:所以n在growth rate上應該比n/(logn)^2大不是嘛？
→ DoubleFish:小弟駑頓～麻煩大大再解釋一下！感激！
推 DoubleFish:謝謝大大解釋～我再研究看看
推 banjmin:有點偏的題目 考到證明的變型 一般都考O(nloglogn)那題
→ kiki86151:人在外面@@ 我回家再解釋 如果有空的話XD
→ ken1325:那答案是什麼？ O(nlog(log^2n)) ?
→ YungMH:答案應該是O(n*loglogn)
→ kiki86151:應該是O(n)吧 我解出來了@@ 另貼文了
推 FRAXIS:1/(i^2)就是Riemann zeta function帶入2的值..
→ FRAXIS:http://en.wikipedia.org/wiki/Basel_problem
→ FRAXIS:當n為無窮大時，其值為pi^2 / 6 所以是一個常數..