[問題] LC 505 tha maze ii

[sean72 (.)]

Leetcode 505. The Maze II 時間複雜度怎麼計算?
這題鎖上了。題目請見這篇：http://www.cnblogs.com/grandyang/p/6725380.html

https://paste.ubuntu.com/p/6rDhmhGsks/
用min heap 代替 queue實現最短路徑
但是我不會估算時間複雜度
請大家解惑

我最早的想法：總共m*n個點，heap裡面最多就是m*n個點，
所以每次彈出的複雜度就是log(m*n) 總共m*n個點，所以是m*n*log(m*n)
每次彈出之後有滾動，
那麼就變成 m*n*log(m*n)*max(m,n)

leetcode solution 解答上寫此方法的時間複雜度為 m*n*log(m*n)
那麼每一個點彈出之後的滾動呢？

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.189.14.17
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1547344143.A.7D1.html
推 ThxThx: 你那樣想不是最小的upper bound
→ ThxThx: 注意到每一個node不會再被塞進heap
→ ThxThx: 而且每次只更新上下左右四個點
→ ThxThx: 這是Dijkstra alg的精髓