[理工] 複雜度分析

[APE36 (PT鄉民)]

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
推 simthree:1.原式=log1+log2+...+logn=log(n!)
→ simthree:其中(n!)>=(n/2)^(n/2)
→ simthree:在兩邊各取log
→ simthree:即可得log(n!)=O(nlogn)
→ simthree:這邊的重點是你要知道(n!)>=(n/2)^(n/2)
推 simthree:2.先依照 常數<對數<線性<多項式<指數<階乘 排大小
→ simthree:再取log將不確定的做大小的比較