作者sean72 (.)
看板Programming
标题Fw: [问题] LC 505 the maze ii 时间复杂度估算
时间Fri Jan 11 12:39:55 2019
※ [本文转录自 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://webptt.com/cn.aspx?n=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