Geek Answers Handbook

Big O by the decision of Dijkstra Fibonacci-heap

From Wikipedia : O(|E| + |V| log|V|)

From the Big Cheet List : O((|V| + |E|) log |V|)

I believe that there is a difference between E + V log V and (E+V) log V , does not exist?

Because if Wikipedia is the right one, should it not be shown as O(|V| log |V|) only then (Removing |E| ) for the reason I don’t understand?)?

What is Big About Dikstra with Fibonacci Heap?

+6
source share
2 answers

The complexity of Dijkstra's shortest path algorithm:

  O(|E| |decrease-key(Q)| + |V| |extract-min(Q)|)

where Q are the ordinal vertices of the queue with the lowest priority according to their current distance estimate.

For the Fibonacci heap and the binary heap, the complexity of the extract-min operation in this queue is O(log |V|) . This explains the total amount |V| log |V| |V| log |V| in total. For a queue implemented with an unsorted array, the extract-min operation will have complexity O(|V|) (the entire queue must be passed), and this part of the sum will be O(|V|^2) .

In the remaining part of the sum (the one with the edge coefficient | E |), O(1) vs The difference O(log |V|) comes precisely from the use of the Fibonacci heap, and not the binary heap, respectively. The operation of the reduction keys, which can occur for each edge, is of such complexity. Thus, the remainder of the sum ultimately has complexity O(|E|) for the Fibonacci heap and O(|E| log |V|) for the binary heap. For a queue implemented with an unsorted array, the key reduction operation will be of constant complexity (the queue directly stores the keys indexed by vertices), and this part of the sum will thus be O(|E|) , which is also O(|V|^2) .

Summarizing:

  • Fibonacci heap: O(|E| + |V| log |V|)
  • binary heap: O((|E| + |V|) log |V|)
  • unsorted array: O(|V|^2)

Since in the general case |E| = O(|V|^2) |E| = O(|V|^2) , this cannot be simplified further without making further assumptions about the graphs under consideration.

+15
source

Dijkstra - O (| E | + | V | log | V |) with a Fibonacci bunch and O ((| V | + | E |) log | V |) without it.

Both are correct in some way. Big O Cheat List showing the most common implementation and Wiki, the best of them.

O (| E | + | V | log | V |) is not in O (| V | log | V |) btw. E is in O (| V | ^ 2), not O (| V | log | V |).

0
source

More articles:


All Articles