→ a127a127:不 原本就是O(n^3) 填一格的時間只要O(1) 08/04 05:22
→ a127a127:並不是對所有k去找 而是在填第k個表時只需要考慮i->k->j 08/04 05:24
→ a127a127:兩個k是相同的 意義上也不是走k步 而是只經過1~k的點 08/04 05:25
※ 引述《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