為什麼這篇時間複雜度證明鄉民發文收入到精華區：因為在時間複雜度證明這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者woody3724 (woody)看板Grad-ProbAsk標題[理工] 演算法 求時間複雜...
時間複雜度證明 在 Fountain 新活水 Instagram 的最讚貼文
2021-07-11 09:09:32
【新活水3月號｜正體字】 ✤「我在這個行業十多年，也在這個行業最大的公司工作過，我很清楚要一個廠商投資在一套正體中文的開發相當困難，原因是中文字實在太多，複雜度和難度也遠比英文字高。」 為解決市場需求，字體公司常見的做法，就是將中文字的部首拆開來做之後再加以組合，這樣就能像生產線製造出的規格化模...
如連結
http://i.imgur.com/1MYHGxt.jpg
綠色字是題目 要求時間複雜度
紫色是我的算法
算到最後
請問 1/(i^2)的級數有公式嗎@@?
謝謝各位
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.240.46
→ ken1325:調和數列 11/09 18:57
推 DoubleFish:我是用Master Method看耶，a=2,b=2,f(n)=n/(logn)^2 11/09 19:58
→ DoubleFish:所以n^log_ab=n，f(n)是1/(logn)^2*n 11/09 20:00
→ DoubleFish:符合case1的情況所以T(n)=θ(n)這樣？ 11/09 20:02
→ kiki86151:這不能用master看 也不是調合數列 應該是O(n) 11/09 20:02
→ DoubleFish:可以請教一下為何不能用master看嘛？ 11/09 20:04
→ kiki86151:用master如果f(n)=n/logn答案是O(n*log(logn))喔非O(n) 11/09 20:06
推 kiki86151:此題解法是1/i^2 積分上n下1就出來了(n-1)/n=O(1) 11/09 20:09
→ kiki86151:跟調合證明很像 就像黎曼面積 1/i積分上n下1 =log(n) 11/09 20:11
→ kiki86151:至於master的話 遇到有f(n)有n^loga_b會有問題(case2) 11/09 20:13
→ kiki86151:所以能不要用其實盡量 像這類題的 用展開或遞迴樹比較好 11/09 20:15
推 DoubleFish:不好意思 題目給的f(n)不是是n/(logn)^2嘛？ 11/09 20:16
→ DoubleFish:所以n在growth rate上應該比n/(logn)^2大不是嘛？ 11/09 20:16
→ DoubleFish:小弟駑頓～麻煩大大再解釋一下！感激！ 11/09 20:16
推 DoubleFish:謝謝大大解釋～我再研究看看 11/09 20:21
推 banjmin:有點偏的題目 考到證明的變型 一般都考O(nloglogn)那題 11/09 20:43
→ kiki86151:人在外面@@ 我回家再解釋 如果有空的話XD 11/09 21:26
→ ken1325:那答案是什麼？ O(nlog(log^2n)) ? 11/09 21:33
→ YungMH:答案應該是O(n*loglogn) 11/09 21:48
→ kiki86151:應該是O(n)吧 我解出來了@@ 另貼文了 11/09 23:03
推 FRAXIS:1/(i^2)就是Riemann zeta function帶入2的值.. 11/10 09:00
→ FRAXIS:當n為無窮大時，其值為pi^2 / 6 所以是一個常數.. 11/10 09:01