Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Re:Dijkstra复杂度到底是多少

Posted by chaeyeon at 2009-02-06 20:39:11
In Reply To:Dijkstra复杂度到底是多少 Posted by:5438 at 2009-02-06 19:29:08

用最小堆来实现， 堆的上浮操作是log(V)的
所以算法复杂是Elog(V)

如果用其它一些堆（比如Fibonacci heap.）上浮操作是均摊O(1)的
所以这块算法是E的。

而每个点要从堆中删除一次。
很不幸的是Fibonacci heap的删除很慢要log(V)所以算法复杂要加个VlogV咯

Followed by:

Re:Dijkstra复杂度到底是多少 (52) 5438 2009-02-07 08:59:03
- Re:Dijkstra复杂度到底是多少 (93) chaeyeon 2009-02-07 10:07:52
  - Re:Dijkstra复杂度到底是多少 (6) 5438 2009-02-07 17:38:55

Post your reply here:

Home Page Go Back To top