作者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/m.aspx?n=bbs/Prob_Solve/M.1547181489.A.0B2.html
※ sean72:轉錄至看板 Programming 01/11 12:39
※ 編輯: sean72 (73.189.14.17), 01/11/2019 14:25:17
1F：推 FRAXIS: 你頂多只有 m*n 個點 m*n*4 條邊 所以你頂多插入 m*n*4 次 01/12 11:40
謝謝你的推文，但我還是不太明白，可以麻煩你再解釋多一些嗎?
計算用heap
但是每次彈出一個點之後，都需要用while loop滾動，這部分怎麼加入估算呢?
※ 編輯: sean72 (73.189.14.17), 01/12/2019 16:16:50
2F：推 FRAXIS: 你滾動的那部份應該可以作 preprocess 吧 01/12 22:59
該如何做preprocess呢?
謝謝
※ 編輯: sean72 (73.189.14.17), 01/13/2019 09:44:31
3F：推 FRAXIS: 一個簡單的方法 就是先把 Graph 直接建起來 01/14 05:40
4F：→ FRAXIS: 每一個點 可以滾動到哪些點 在搜尋之前先建好 01/14 05:40
5F：→ FRAXIS: 在建的時候要有技巧 因為點 u 朝方向 d 最終滾到 v 的話 01/14 05:41
6F：→ FRAXIS: 那 u ~ v 上面的所有點 向 d 滾動必定也都會滾到 v 01/14 05:41
7F：→ FRAXIS: 利用這個性質就可以避免重複計算 01/14 05:42
8F：→ FRAXIS: 然後在搜尋的時候就可以不用計算滾動了 01/14 05:42
9F：→ FRAXIS: 要加速的話 就一邊搜尋一邊建圖 01/14 05:43
10F：→ FRAXIS: 或是用 A* 搜尋，這種 2D Grid Graph 的 Heuristic 01/14 05:44
11F：→ FRAXIS: 已經有很多人研究過了 01/14 05:44