Content deleted Content added
→Complexity with Fibonacci heaps: new section |
|||
Line 39:
A paragraph in the Description advises "in pencil, mark the road with an arrow pointing to the relabeled intersection." The next paragraph talks about a visited node's "parent." I think these are talking about the same thing, but it's not very clear. Perhaps better wording might be "by following the nodes' parents ''(that is, traversing the arrows backward)''", or perhaps in the first paragraph, "mark the road with an arrow pointing to the relabeled intersection ''(from 'parent' to 'child')''"
--[[User:Jackrepenning|Jackrepenning]] ([[User talk:Jackrepenning|talk]]) 18:54, 24 September 2016 (UTC)
== Complexity with Fibonacci heaps ==
A few users have been changing the complexity with Fibonacci heaps from <math>O(|E| + |V| \log|V|)</math> to <math>O((|E| + |V|) \log|V|)</math> without any justification. The former appears to be correct based on the reasoning in the article:
:For any implementation of the vertex set {{mvar|Q}}, the running time is in
::<math>O(|E| \cdot T_\mathrm{dk} + |V| \cdot T_\mathrm{em})</math>,
:where <math>T_\mathrm{dk}</math> and <math>T_\mathrm{em}</math> are the complexities of the ''decrease-key'' and ''extract-minimum'' operations in {{mvar|Q}}, respectively.
since <math>T_\mathrm{dk} = \Theta(1)</math> for Fibonacci heaps.
Hence I am reverting the complexity with Fibonacci heaps back to <math>O(|E| + |V| \log|V|)</math>. -- [[User:Paddu|Paddu]] ([[User talk:Paddu|talk]]) 15:44, 27 December 2017 (UTC)
| |||