English 字幕

← 02-09 Big-Theta


Showing Revision 1 created 07/07/2012 by Amara Bot.

  1. In that last analysis of grid graphs,
  2. we ended up discovering that the number of edges is 2n - 2√n,
  3. which is such a terrible function, but the fact of the matter is
  4. as these analyses get more and more complicted
  5. getting detailed answers like this is more and more cumbersome.
  6. Researchers have worked out a scheme for talking about functions in a much more
  7. high level way while still being completely rigorous but without it getting bogged down
  8. in all the details, and this is the notion of asymptotic growth.
  9. You may have heard it described in the form of Big Oh notation,
  10. and we're going to get to Big Oh in a moment, but we need to start off with Big Theta.
  11. Θ(g(n)) is actually a set of functions, specifically the set of functions that grow
  12. equally quickly as g(n).
  13. To be a bit more formal about it, we say that some function f(n) is in the set
  14. of functions equally fast growing as g(n),
  15. if and only if there are some constants c1 and c2 and some threshold n0
  16. such that for any n bigger than n0, we have something that looks like this--
  17. the function f(n) for all these values of n--all these big values of n--
  18. is sandwiched between c1 * g(n) and c2 * g(n).
  19. To illustrate this idea with a picture imagine we have some function f(n).
  20. It grows. As n gets bigger, f(n) gets bigger.
  21. We also have some function g(n) that we can multiply by c1 or we can multiply
  22. by some bigger number c2.
  23. What we find is that once we get out to the right of some threshold n0
  24. f(n) is always between c2g(n) and c1g(n).
  25. In the beginning maybe weird things happen, but once we get out far enough asymptotically
  26. in the limit as things get really big, f(n) lies between c2g(n) and c1g(n).
  27. If that's the case, if such c1, c2, and n0 exist, then we can say that f(n) is in Θ(g(n)).