Re: [閒聊] 資訊處理已哭
跟大家分享一下cormen的習題解法
by taking logs: log(logn)! = theta(logn loglogn) by Stirling approximation
可以得到(log n)! = w(n^3) 跟前面emstarbucks版友推文解的方式滿像的 用Stirlings
^^^^ e大是推 O(n^loglogn) 一個用大O 一個是小w
看起來都是化簡後 丟到指數 整理成指數項在成長
cormen習題中複雜度的比較大小好像都是化成很明顯看出的形式
例如
化簡到最後 O(n^3) vs O(2n)
就會直接用一個是指數 一個是多項式 然後直接比大小
如果很難化簡的也會用極限的方式去比較
就像前一篇版友chieya大 提到的用極限的方式
比較複雜度好像本來就有4~5種方法
若過程有道理 答案正確應該都有分吧 (祈禱)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 23.94.68.101
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1437193671.A.50E.html
※ 編輯: RedJessy (23.94.68.101), 07/18/2015 12:34:18
討論串 (同標題文章)