Re: [問題] Floyd演算法的一個題目

看板Prob_Solve (計算數學 Problem Solving)作者 (再一次重來...)時間16年前 (2008/08/03 22:22), 編輯推噓0(003)
留言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
不 原本就是O(n^3) 填一格的時間只要O(1)
08/04 05:22, 1F

08/04 05:24, , 2F
並不是對所有k去找 而是在填第k個表時只需要考慮i->k->j
08/04 05:24, 2F

08/04 05:25, , 3F
兩個k是相同的 意義上也不是走k步 而是只經過1~k的點
08/04 05:25, 3F
文章代碼(AID): #18bRyB46 (Prob_Solve)
文章代碼(AID): #18bRyB46 (Prob_Solve)