Difference between pages "4.21" and "8.25"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
(Created page with "the general form of this problem is to find the kth largest value. finding the median is when k = n/2. to find the kth largest value, * select a partition element and split...")
 
(Created page with "Step 1: Perform topological sorting of the graph (we can do it as Graph is acyclic). This is O(n + m) Step 2: Go through vertices in topological order. Initially all vertic...")
 
Line 1: Line 1:
−
the general form of this problem is to find the kth largest value.  finding the median is when k = n/2.
+
Step 1:
  
−
to find the kth largest value,
+
Perform topological sorting of the graph (we can do it as Graph is acyclic). This is O(n + m)
−
* select a partition element and split the array into 2 sub-arrays - one with the elements smaller than the partition and one with the elements larger than the partition. '''O(n)'''
 
−
* if the array with the elements larger than the partition has k - 1 elements, the partition is the kth largest element
 
−
* if the array with the elements larger than the partition has >= k elements, recurse with the same value of k using the larger elements as the new array. '''O(n/2)''' (average case)
 
−
* else the median is in the array with elements smaller than the partition so adjust k to account for the large elements being discarded and recurse using the smaller elements as the new array '''O(n/2)''' (average case)
 
  
−
the overall complexity is O(n) since
+
Step 2:
  
−
O(n) + O(n/2) + O(n/4) + ... approaches O(2n) which is just O(n) since 2 is a constant.
+
Go through vertices in topological order. Initially all vertices marked as inaccessible and only starting vertex marked with 0 distance.
 +
For every vertex in cycle, if it is accessible, we update all its children with new distance if new distance is shorter then previous one.
 +
Topological sorting ensures that we don't ever need to go backtrack. This is O(n + m).
  
 +
Total running bound is O(n+m), which is linear as requested.
  
−
Back to [[Chapter 4]]
+
 
 +
Back to [[Chapter 8]]

Latest revision as of 14:11, 21 September 2020

Step 1:

Perform topological sorting of the graph (we can do it as Graph is acyclic). This is O(n + m)

Step 2:

Go through vertices in topological order. Initially all vertices marked as inaccessible and only starting vertex marked with 0 distance. For every vertex in cycle, if it is accessible, we update all its children with new distance if new distance is shorter then previous one. Topological sorting ensures that we don't ever need to go backtrack. This is O(n + m).

Total running bound is O(n+m), which is linear as requested.


Back to Chapter 8

Retrieved from "https://algorist.com//algowiki/index.php?title=4.21&oldid=430"