[理工] 105 台 資演

[haniwang (hani)]

想請問c小題設定那個範圍會有什麼影響
https://i.imgur.com/03img89.jpg

想請問第4題的a b小題怎麼算
https://i.imgur.com/FChqr7h.jpg

麻煩各位了！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.0.113
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549441347.A.761.html
→ GeniusPuddin: 下面看起來是第3題? c小題那個就是你一直展開n
→ GeniusPuddin: 最後當n<=sqrt(M)的時候T值會碰到M
→ GeniusPuddin: 總之就答案的複雜度會包含n,M摟
→ JKLee: c小題，可以先假設n=sqrt(M)*2^k
→ JKLee: 接著畫recursive tree
→ JKLee: tree的第i層的時間為big-theta(1)*8^i
→ JKLee: 但最後一層，也就是第k層的時間為T(sqrt(M))*8^k=M*8^k
→ JKLee: 最後把每一層的時間加總
→ JKLee: 仔細觀察，你會發現當n介於這個範圍時:
→ JKLee: sqrt(M)*2^(k-1)<n<=sqrt(M)*2^k
→ JKLee: 不會改變tree的高度，tree的層數依舊為k層
→ haniwang: 感謝兩位！