※ [本文轉錄自 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) <