作者haniwang (hani)
看板Grad-ProbAsk
標題[理工] 105 台 資演
時間Wed Feb 6 16:22:24 2019
想請問c小題設定那個範圍會有什麼影響
https://i.imgur.com/03img89.jpg
想請問第4題的a b小題怎麼算
https://i.imgur.com/FChqr7h.jpg
麻煩各位了！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.0.113
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1549441347.A.761.html
1F：→ GeniusPuddin: 下面看起來是第3題? c小題那個就是你一直展開n 02/06 22:56
2F：→ GeniusPuddin: 最後當n<=sqrt(M)的時候T值會碰到M 02/06 22:57
3F：→ GeniusPuddin: 總之就答案的複雜度會包含n,M摟 02/06 22:57
4F：→ JKLee: c小題，可以先假設n=sqrt(M)*2^k 02/07 07:40
5F：→ JKLee: 接著畫recursive tree 02/07 07:41
6F：→ JKLee: tree的第i層的時間為big-theta(1)*8^i 02/07 07:44
7F：→ JKLee: 但最後一層，也就是第k層的時間為T(sqrt(M))*8^k=M*8^k 02/07 07:47
8F：→ JKLee: 最後把每一層的時間加總 02/07 07:47
9F：→ JKLee: 仔細觀察，你會發現當n介於這個範圍時: 02/07 07:53
10F：→ JKLee: sqrt(M)*2^(k-1)<n<=sqrt(M)*2^k 02/07 07:53
11F：→ JKLee: 不會改變tree的高度，tree的層數依舊為k層 02/07 07:53
12F：→ haniwang: 感謝兩位！ 02/07 17:22