[理工] 105 台 資演

看板Grad-ProbAsk作者 (hani)時間6年前 (2019/02/06 16:22), 編輯推噓0(0推 0噓 12→)
留言12則, 3人參與, 6年前最新討論串1/1
想請問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
→
02/06 22:56, 6年前 , 1F
下面看起來是第3題? c小題那個就是你一直展開n
02/06 22:56, 1F
→
02/06 22:57, 6年前 , 2F
最後當n<=sqrt(M)的時候T值會碰到M
02/06 22:57, 2F
→
02/06 22:57, 6年前 , 3F
總之就答案的複雜度會包含n,M摟
02/06 22:57, 3F
→
02/07 07:40, 6年前 , 4F
c小題，可以先假設n=sqrt(M)*2^k
02/07 07:40, 4F
→
02/07 07:41, 6年前 , 5F
接著畫recursive tree
02/07 07:41, 5F
→
02/07 07:44, 6年前 , 6F
tree的第i層的時間為big-theta(1)*8^i
02/07 07:44, 6F
→
02/07 07:47, 6年前 , 7F
但最後一層，也就是第k層的時間為T(sqrt(M))*8^k=M*8^k
02/07 07:47, 7F
→
02/07 07:47, 6年前 , 8F
最後把每一層的時間加總
02/07 07:47, 8F
→
02/07 07:53, 6年前 , 9F
仔細觀察，你會發現當n介於這個範圍時:
02/07 07:53, 9F
→
02/07 07:53, 6年前 , 10F
sqrt(M)*2^(k-1)<n<=sqrt(M)*2^k
02/07 07:53, 10F
→
02/07 07:53, 6年前 , 11F
不會改變tree的高度，tree的層數依舊為k層
02/07 07:53, 11F
→
02/07 17:22, 6年前 , 12F
感謝兩位！
02/07 17:22, 12F
‣ 更多 haniwang 的文章
文章代碼(AID): #1SMfb3TX (Grad-ProbAsk)