[理工][algo][演算] 時間複雜度 , 不能以maste …

看板Grad-ProbAsk作者 (想玩音樂)時間14年前 (2011/06/16 20:31), 編輯推噓1(1推 0噓 1→)
留言2則, 2人參與, 最新討論串1/2 (看更多)
關於不能以 master theorem 算複雜度的 case 爬文看到網址如下 http://algnotes.wordpress.com/2010/05/30/time-complexity-substitution-method/ 然後再 I2A ch 4-6 後面有喵到相關問題 (page 108) 但是只有問題沒有解題說明 想請教一下這部分的解決概念 可以在哪本書看到呢 或者, 只能用我上面貼的link,它裡面的方式 來解題嗎? 因為algo部分是自己K的 所以蠻怕有觀念漏掉的地方 謝謝! 第二個問題 97 交大資訊 assume n<=2 , 解 tight asymptotic upper bound T(n) = T(n-1) + 1/n 解答是給 Θ(lgn) 但我想不到過程 尤其是 1/x 部分要怎麼解 謝謝各位強者<(_ _)> -- No time to pray.... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.128.126.145 ※ 編輯: metalalive 來自: 220.128.126.145 (06/16 20:43)
推
06/16 20:59, , 1F
帶入之後 是一個調和級數
06/16 20:59, 1F
→
06/16 20:59, , 2F
這應該是解sigma(1/x)的問題吧....微積分應該有學過喔
06/16 20:59, 2F
‣ 更多 metalalive 的文章
文章代碼(AID): #1D-VUhpy (Grad-ProbAsk)
‣ 更多 metalalive 的文章
文章代碼(AID): #1D-VUhpy (Grad-ProbAsk)