作者netsphere (再一次重来...)
看板Prob_Solve
标题Re: [问题] Floyd演算法的一个题目
时间Sun Aug 3 22:22:00 2008
※ 引述《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
1F：→ a127a127:不 原本就是O(n^3) 填一格的时间只要O(1) 08/04 05:22
2F：→ a127a127:并不是对所有k去找 而是在填第k个表时只需要考虑i->k->j 08/04 05:24
3F：→ a127a127:两个k是相同的 意义上也不是走k步 而是只经过1~k的点 08/04 05:25