English 字幕

← Big-Theta Examples - Intro to Algorithms


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

  1. What the Big Theta allows us to do is basically write complicated functions
  2. in a much simpler way.
  3. We can take a function like ½n² and just think of it as Θ(n²).
  4. And 8√n we can think of a just Θ(√n).
  5. Our equation from before, 2n - 2√n just becomes Θ(n).
  6. It's just a linear function asymptotically.
  7. A complicated expression like this where we have n⁴, which is the term that grows the fastest,
  8. becomes Θ(n).
  9. The ln n--in fact, any base log n is Big Theta of any other base log n as long as it's a constant.
  10. I like to think in terms of base 2 logs, because I'm a computer scientist.
  11. That's what we do.
  12. π² is something that doesn't grow with n, and it ends up being in the set Θ(1).
  13. It's just another constant.
  14. Just to beat this dead horse a little bit longer, let's use the definition of Big Theta
  15. to show that this expression that we determine for the growth in edges in a grid--
  16. 2n - 2√n--really is just a linear function. It grows like Θ(n).
  17. The game plan is that we need to find constant c₁ and c₂--bigger than 0
  18. and a threshold N₀ so that for all the n bigger than n₀, the function that we care about
  19. is sandwiched between these two scalings.
  20. Let's focus on this one first.
  21. What c₂ can we plug in here so that we're guaranteed that this will be above this expression.
  22. If we just copy this inequality down just flipping it around to make it a little easier to think about,
  23. we want c₂ so that c₂n is bigger than this. Divide through by n
  24. Now we need a c₂ that is bigger than 2 minus something that's actually growing.
  25. Two should work for that.
  26. If we set c₂ to 2, it will satisfy this inequality.
  27. Let's just summarize all that
  28. We can set c₂ = 2. What about c₁?
  29. Well, let's take c₁ to be 1.
  30. Intuitively, the idea being this function is growing like 2n minus something smaller than that.
  31. So, n should be underneath that.
  32. But let's just make show if c₁ is equal to 1, then we need n to be less than or equal
  33. to this expression. For what values of n is that going to be true?
  34. It's not true of all of them, but it's true for some of them.
  35. We can add 2√n to both sides, subtract n from both sides, and we get that.
  36. If we divide through by √n, we get 2 ≤ n/√n and divided by √n is actually √n.
  37. So, we have 2 ≤ √n.
  38. We square both sides. We have 4 ≤ n, or--flipping that around the other way--
  39. if n ≥ 4, then this is true
  40. That means we have to throw away the smaller values of n,
  41. and we can do that very simply by setting n₀ to 4.
  42. This only has to hold for n that are bigger than n₀.
  43. That's what we've got there.
  44. There we have it.
  45. If we set the constants this way, n₀, c₁, and c₂, then what we find is
  46. that for big enough n this more complicated expression is sandwiched between
  47. two simple linear functions or to say it another way--