Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Running Time of Connected Component - Intro to Algorithms

Get Embed Code
3 Languages

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

  1. It's important to analyze the running time of this algorithm
  2. so we have some idea of how efficient it is.
  3. And again, that's going to involve counting up the number of primitive steps,
  4. primitive statements, time that the algorithm takes when solving a problem.
  5. We'll assume, as before, that n represents the number of nodes in the graph
  6. and m represents the number of edges.
  7. And it turns out that the basic strategy that we use for this algorithm
  8. is a kind of graph search.
  9. There's 2 principal flavors of graft search, depth first search and breadth first search.
  10. This one that we've been talking about is a form of depth first search.
  11. Later we're going to see a version of breadth first search
  12. when we start looking at shortest paths.
  13. But this particular algorithm is not concerned about the length of the paths,
  14. it's just trying to figure out which nodes can be reached by any kind of path.
  15. So taking a look at this algorithm here,
  16. one of the things that we can note right off the bat
  17. is statements like this one, marked(node) = True,
  18. can only be executed once for each node in the graph.
  19. So even though it's a little bit hard to tell exactly when this is going to execute,
  20. we know at the end of the day every node is going to get marked
  21. and no node is going to get marked twice.
  22. So that means once for each node in the graph we're going to execute this statement
  23. and this statement and this loop.
  24. And what does this loop do?
  25. It goes through and basically visits all the edges that come out of this particular node (node).
  26. And for each of those edges, well, it does some work.
  27. It checks whether or not it's marked, which we're going to assume is a unit time operation,
  28. some kind of nice hash table and it behaves nicely,
  29. and a recursive call, and we're going to somehow have to account for
  30. all the stuff that happens in this recursive call, but let's not worry about that for the moment.
  31. It's going to do this one main computation, this adding whatever value it gets back
  32. to this quantity here, then it returns.
  33. So these statements here are going to get executed once per node.
  34. This statement is going to get executed once per node.
  35. This statement is going to get executed once per edge in the graph
  36. because for each node it's going to visit all the edges emanating from that node.
  37. So even though it's very difficult to keep track of what's going to be executed when,
  38. we know that the total running time here is going to be big theta
  39. of the number of nodes plus the total number of edges in the graph.
  40. So that's what's happening in this marked component.
  41. And then what's happening outside here, this marked gets executed once at all,
  42. then for every node in the graph it may or may not execute this statement,
  43. which does the call to mark component.
  44. So we're going to iterate over all the nodes,
  45. and again, we're going to do some work but not more than constant work per node.
  46. And if we look at our running time here, adding another n in here doesn't change the big theta.
  47. Again, even though it's very complex to figure out which statements are executing when,
  48. the actual running time is big theta of n + m.
  49. It's worth pointing out that this is linear in the size of the graph.
  50. The graph consists of some number of nodes and some number of edges,
  51. and that's the whole story.
  52. So this is actually linear in the size of the graph.