[理工] 複雜度分析

看板Grad-ProbAsk作者 (PT鄉民)時間11年前 (2014/07/19 16:31), 編輯推噓2(205)
留言7則, 1人參與, 最新討論串1/1
http://ppt.cc/Veoq 請益第一題該怎麼倒出證明這項式子成立? 需用到積分來表達?? 關於第二小題,有無較快方法可以判斷出大小的問題!! 有變化題感覺就蠻難判斷的了!! THANKS!! -- ◢ ◣ ▊ ▊ ▊ ▊ ◢◣ ◢◣ ▊ ▊ ▊███ ◣ ◣ ◢█ L I N ◣ ▊ ▊ █◣ ▊◢ ◥◣ ▊ ▊ █◣ ▊ ▊ ▊ ▊ ▊ ◥◤ ▊ ▇▇ ◥◤ ▊ ▊ ▊◥◣▊◥ ▊ ▊▊◥◣▊ ▊ ▊ ▊ ▊ ▊ ▊ ▊ ▊ ▊ ◥▊ ◥◣ ▊ ▊▊ ◥▊ ▊ ▊ ▉ ▉ ▊ ▊ ▊ ▊ ◥◣█▆▆▊▊ ▊ ▊ ▊ ◥█ ψ █▇▇ ▊ ▊ ▊◣▅▇◤▊ ▊▊ ▊ ▊ ▊ ▊ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.123.248 ※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1405758695.A.E6D.html

07/19 17:51, , 1F
1.原式=log1+log2+...+logn=log(n!)
07/19 17:51, 1F

07/19 17:52, , 2F
其中(n!)>=(n/2)^(n/2)
07/19 17:52, 2F

07/19 17:52, , 3F
在兩邊各取log
07/19 17:52, 3F

07/19 17:53, , 4F
即可得log(n!)=O(nlogn)
07/19 17:53, 4F

07/19 17:53, , 5F
這邊的重點是你要知道(n!)>=(n/2)^(n/2)
07/19 17:53, 5F

07/19 17:57, , 6F
2.先依照 常數<對數<線性<多項式<指數<階乘 排大小
07/19 17:57, 6F

07/19 17:58, , 7F
再取log將不確定的做大小的比較
07/19 17:58, 7F
文章代碼(AID): #1JoYpdvj (Grad-ProbAsk)