作者sean72 (.)
看板Python
标题[问题] LC 505 tha maze ii
时间Sun Jan 13 09:48:58 2019
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://webptt.com/cn.aspx?n=bbs/Python/M.1547344143.A.7D1.html
1F：推 ThxThx: 你那样想不是最小的upper bound 01/13 11:13
2F：→ ThxThx: 注意到每一个node不会再被塞进heap 01/13 11:13
3F：→ ThxThx: 而且每次只更新上下左右四个点 01/13 11:13
4F：→ ThxThx: 这是Dijkstra alg的精髓 01/13 11:13