English 字幕

← Running Time - Intro to Algorithms


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

  1. What I'd like you to think about is how long does it take for naïve(a, b)
  2. to execute as we look at larger and larger inputs.
  3. These should be really fast. This should still be pretty fast.
  4. As we give it larger and larger powers of 2,
  5. you should notice that it's going to take longer and longer
  6. for this multiplication to actually execute.
  7. Now, I could keep doing this all day, which probably wouldn't be fun for any of us.
  8. What I'll do instead is have the computer actually do some of these calculations for me.
  9. I'll measure the time and then we'll plot it and see how it turns out.
  10. Here's our naïve algorithm again.
  11. There's a whole lot of Python code wrapped around it that's going to help us do some plotting
  12. What we're going to do is we're going to run naïve(n, n) with different values of n.
  13. The n's are going to be all the powers of 2 from 2^0 to 2^23.
  14. For each of those what we're going to do--and the details of this aren't important--
  15. we're going to time how long it takes to do that, gather all those times together,
  16. and then plot them. Here we go. We run this.
  17. It generated a plot, and this is what that plot looks like.
  18. It's a little bit crufty to read at the bottom,
  19. but you can get a sense of the general shape of it.
  20. Across this access is the number that we're squaring.
  21. We're sending naive of this number, and it goes up to billions.
  22. This is the time in seconds that it takes for it to execute.
  23. You can see that it actually follows a very recognizable pattern.
  24. Our plot looks something like this.
  25. How does the running time t relate to the input that we're giving naive n?
  26. Is the running time roughly constant--
  27. as n gets bigger the time stays about the same?
  28. Is it roughly logarithmic--as n gets bigger the time grows like the log of n?
  29. Is it roughly linear--as n gets bigger the time grows like cn for some constant c?
  30. Or is it roughly exponential where the time grows like c^n for some value of c?