Fw: [問題] LC 505 the maze ii 時間複雜度估算

看板Programming作者sean72 (.)時間5年前 (2019/01/11 12:39)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/1

※ [本文轉錄自 Prob_Solve 看板 #1SE1sn2o ] 作者: sean72 (.) 看板: Prob_Solve 標題: [問題] LC 505 the maze ii 時間複雜度估算時間: Fri Jan 11 12:38:04 2019 Leetcode 505. The Maze II 時間複雜度怎麼計算? 這題鎖上了。題目請見這篇：http://www.cnblogs.com/grandyang/p/6725380.html leetcde 解法1 每個點不斷的暴力更新 https://paste.ubuntu.com/p/mdmfBFFgJf/ 每次bfs的時候加一層while loop來模擬滾動 time complexity m*n*max(m,n) 我的理解：總共m*n個點，每個點都有m or n的滾動的可能 (這應該正確吧?) leetcde 解法2 用一個heap來代替que以實現最短路徑 https://paste.ubuntu.com/p/HP5v93dQKf/ 我最早的想法：總共m*n個點，heap裡面最多就是m*n，所以每次彈出的複雜度就是log(m*n) 總共m*n個點，所以是m*n*log(m*n) 每次彈出之後有滾動，那麼就變成 m*n*log(m*n)*max(m,n) (很明顯不對，這樣就比上面的暴力還慢) 解答上寫 m*n*log(m*n) <-- 那麼每一個點彈出之後的滾動呢？謝謝大家的回答 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.189.14.17 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1547181489.A.0B2.html ※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: sean72 (73.189.14.17), 01/11/2019 12:39:55 ※ 編輯: sean72 (73.189.14.17), 01/11/2019 14:25:01