3
$\begingroup$

I knew the time complexity of Topological ordering is O(V+E) since we don't need to do sorting during the selection of node whose incoming degree is 0. But what about the least topological ordering that make sure every node to delete is always the least one of the List of 0 incoming degree nodes. Like the picture show below, "1 2 4 3 5" and "2 1 4 3 5" are both topological ordering but the least one is "1 2 4 3 5".
enter image description here

I store the 0 incoming degree nodes in a priority queue(min-Heap) and delete the top of it every time. So there are totally V nodes to delete and every delete needs the priority queue O(log V) to adjust to keep itself a min-Heap. It seems that the total node deletion is O(VlogV) while the basic topological ordering is O(V+E). What is the exactly time complexity of The least topological ordering? Is it O(VlogV+E)? Hope you can help me!

$\endgroup$
1
  • 1
    $\begingroup$ Hi San Zhang, welcome to Stack Overflow! This site is for questions relating to programming, and while algorithms and time complexity are certainly related, you may find more help at our sister site Computer Science Stack Exchange. $\endgroup$
    – AAM111
    Apr 2 at 9:42

2 Answers 2

2
$\begingroup$

Yes, the best complexity one can get for this problem is O(V*log(V) + E). Therefore, your approach is correct. Congrats :)

From a practical standpoint, the average time will be much closer to O(V + E), as the vast majority of test cases will not require more than sqrt(V) nodes to be in the priority queue at any given point.

However, if you really want to get the best performance on this problem (practical, that is, as the complexity will stay the same) you can implement it using a Fibonacci Heap. This would often give you an amortised complexity for the node deletion, but it comes with its overhead and it's harder to implement. Nonetheless, this is an advanced concept beyond the scope of this question and I'll just link it below. https://en.wikipedia.org/wiki/Fibonacci_heap#:~:text=In%20computer%20science%2C%20a%20Fibonacci,binary%20heap%20and%20binomial%20heap.

Hope this helps!

$\endgroup$
2
  • $\begingroup$ You cannot delete from Fibonacci heap in O(1) amortized. $\endgroup$ Apr 3 at 23:37
  • $\begingroup$ Fibonacci heap is not good for best performance practically, especially here we only using simple insert/delete-min operations. $\endgroup$
    – pcpthm
    Apr 4 at 4:25
0
$\begingroup$

The $\Omega(N \log N)$ time complexity bound applies to comparison-based algorithms, but faster algorithms are possible if the elements are integers and when we are using a RAM model.

Indeed, by using van Emde Boas tree as the priority queue in the topological sorting algorithm, we get $O(V \log \log V + E)$ time complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.