课程: AI Algorithms for Game Design with Python

免费学习该课程！

今天就开通帐号，24,700 门业界名师课程任您挑！

A word on complexity

A word on complexity - Python教程

课程: AI Algorithms for Game Design with Python

开始一个月试用 购买团队方案

A word on complexity

“

- [Instructor] Since we've already seen a scary scenario for these algorithms, it's important to get a sense of how well our algorithms will work. So let's talk about the complexity of minimax. Suppose we have a search tree with a constant branching factor B and a maximum depth M. In other words, each state has B possible moves and the game goes on for M turns. Well, the time complexity of minimax is O of B to the M and its space complexity is O of M. Now, this is a synthetic notation, so these are not exact expressions for the running time or the memory needed by the algorithm. Instead, these expressions refer to an upper bound of how the running time or the memory requirement grows as B or M grow. As you can see, the time complexity is exponential just as you might have expected. Minimax takes billions of years to produce one move. This is because at each level we have B more possible states to analyze, and this will go on for M turns. Increasing M by one makes the three B times…

内容