English subtitles

← 13-09 Time Complexity Question

Unit 13 09 Time Complexity Question.mp4

Get Embed Code
2 Languages

Showing Revision 1 created 11/28/2012 by Amara Bot.

  1. Now we know we have an algorithm that can solve any game tree,
  2. that can propagate the terminal values back up to the top
  3. and tell us the value for any position.
  4. It's theoretically complete, but now we need to know
  5. the complexity of the algorithm to figure out if it's practical.
  6. Let's look at an analysis of how long it's going to take.
  7. Let's say that the average branching factor--
  8. the number of possible moves or actions coming out of a position--is b.
  9. Here b would be 4.
  10. And let's say that the depth of the tree is m, so b wide and m deep.
  11. Now what I want you to tell me is what would be the computational complexity
  12. of searching through all the paths and backing the values up to the top.
  13. Would it be of the order of b times m or the order of be to the mth power
  14. or the order of m to the b power? Chose one of these.