※ [本文转录自 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) <