[理工] 複雜度分析
作者: APE36 (PT鄉民) 2014-07-19 16:31:32
請益第一題該怎麼倒出證明這項式子成立?
需用到積分來表達??
關於第二小題，有無較快方法可以判斷出大小的問題!!
有變化題感覺就蠻難判斷的了!!
THANKS!!
作者: simthree (jeff) 2014-07-19 17:51:00
1.原式=log1+log2+...+logn=log(n!)其中(n!)>=(n/2)^(n/2)在兩邊各取log即可得log(n!)=O(nlogn)這邊的重點是你要知道(n!)>=(n/2)^(n/2)2.先依照 常數<對數<線性<多項式<指數<階乘 排大小再取log將不確定的做大小的比較