[理工] 清大101 科學

看板Grad-ProbAsk作者 (see u)時間11年前 (2013/01/24 22:19), 編輯推噓2(2推 0噓 15→)
留言17則, 7人參與, 最新討論串1/1
請問 清大 6. (logn!) 和 logn^(logn) 要怎麼比較 13. (b) 可以問答案是yes還是no 14. 要怎寫比較好 碰到這類reduced都會卡住 附上題目網址 http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/101/2001.pdf -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 106.1.90.234
→
01/24 22:23, , 1F
6. 兩邊取log
01/24 22:23, 1F
→
01/24 22:26, , 2F
取完是一樣嗎?
01/24 22:26, 2F
→
01/24 22:28, , 3F
我跟同學算取完是一樣 但是洪捷書上寫log^logn比較大
01/24 22:28, 3F
→
01/24 22:37, , 4F
我都把logn當成n
01/24 22:37, 4F
推
01/25 01:24, , 5F
6. log(logn!)=log(nlogn)=logn+loglogn=O(logn)
01/25 01:24, 5F
→
01/25 11:27, , 6F
(logn)! 用 stirling 公式解
01/25 11:27, 6F
→
01/25 11:29, , 7F
看洪捷不如直接看 CLRS,洪捷很多觀念都寫的不清楚
01/25 11:29, 7F
→
01/25 16:01, , 8F
P's minimized n-tupple is c1=P
01/25 16:01, 8F
→
01/25 16:01, , 9F
if min(P's min-n-tuple) == P then P is prime
01/25 16:01, 9F
→
01/25 16:54, , 10F
13是yes 用greedy method每次取貢獻最多的subset
01/25 16:54, 10F
→
01/25 16:56, , 11F
複雜度是O(n^3) 因為si都只有2個元素,與C(n,2)=O(n^2)
01/25 16:56, 11F
→
01/25 16:57, , 12F
跟universe set比較是O(n) 總共就是O(n^3)
01/25 16:57, 12F
→
01/25 17:36, , 13F
更正:因為每次最少只會貢獻1個元素,所以上面這個過程要進行
01/25 17:36, 13F
→
01/25 17:37, , 14F
O(n)次,所以總共是O(n^4)
01/25 17:37, 14F
→
01/25 19:08, , 15F
感謝樓上
01/25 19:08, 15F
推
02/02 21:10, , 16F
13題是false...
02/02 21:10, 16F
→
02/02 21:13, , 17F
(A)
02/02 21:13, 17F
‣ 更多 yoie 的文章
文章代碼(AID): #1H0KC409 (Grad-ProbAsk)