English subtitles

← Using Heaps - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. As I was describing it before, for each node we do this test to find the shortest distance so far.
  2. That's a heap operation--there's n things in the heap, so this is a logn operation.
  3. So this altogether is going to get run once for each node--so this part of the algorithm
  4. actually takes time and logn.
  5. For each of the edges in the graph, we do this distance reduction operation,
  6. which also is a logn time operation--so that becomes for each edge a logn or mlogn.
  7. Now, both of these have to get done so we actually add these together nlogn and mlogn,
  8. and into the assumption that the graph is connected, this m has to be at least as big as this n--
  9. because this term dominates--so that gives us a total running time of Î(mlogn).
  10. Just I'll mention as an aside, there're some very clever data structure work that's been done
  11. by Fredman and Tarjan, the same Tarjan as before, that allows this actually to be decreased
  12. using a very special kind of heap that allows the running time to become nlogn+m.
  13. We need at least m just to visit all the edges. So this is a pretty remarkable result.
  14. I've implemented this in the past. It didn't run so fast for me.
  15. These are asymptotic results in that the overhead in keeping this fancy heap type
  16. structure updated was more than--well, I wasn't able to implement it so it was efficient enough.
  17. But the heaps that we were talking about the overhead is pretty raw
  18. and we get this kind of running time, the elapse should be pretty efficient.