Re: [問題] Floyd演算法的一個題目
看板Prob_Solve (計算數學 Problem Solving)作者netsphere (再一次重來...)時間16年前 (2008/08/03 22:22)推噓0(0推 0噓 3→)留言3則, 1人參與討論串3/4 (看更多)
※ 引述《netsphere (再一次重來...)》之銘言:
: : 如圖:http://www.badongo.com/pic/4102668
: 有點懶的算~ 叫程式幫你算吧 http://rafb.net/p/zgvUbv26.html
: 其實我也有個問題要問 >///<
: 遞迴式: distk(i,j)=Min(distk-1(i,j),distk-1(i, k)+distk-1(k, j))
: 直接用遞迴式定義來寫是 O(n^4) 我的程式就是.....
: 為什麼可以壓到O(n^3) 是那裡偷吃步了?
不懂怎麼證明.....Orz
先說一下 我對Dn的定義 Dn是表從i走n步到j的最短距離的矩陣Mij
後來想了一下能壓到 O(n^3) 是因為直接建立 Dn-1 的矩陣
偷吃了建立 D1 D2 ....Dn-2 的時間
如果一般人照觀念寫出來應該都是O(n^4) XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.118.84.152
→
08/04 05:22, , 1F
08/04 05:22, 1F
→
08/04 05:24, , 2F
08/04 05:24, 2F
→
08/04 05:25, , 3F
08/04 05:25, 3F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章